单链表常见算法题（全）_单链表算法题

---

前言

所有题来源于Leetcode，我想利用这个博客记录我的思考过程。

力扣上的头结点介绍

力扣题上的单链表是没有表头的，也就是第零个结点。题里的头结点指第一个数据结点。
一般我们说的头结点是第零个结点，也称为哑结点(dummy node)或表头(header)。
为了不产生歧义，第零个结点本文统一称为哑结点(dummy node)，题里的头结点指第一个数据结点。
而指向哑结点的指针，我统一命名为dummyHead。

---

题目

1.移除链表元素（203题）

问题描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例2：
输入：head = [], val = 1
输出：[]
示例3：
输入：head = [7,7,7,7], val = 7
输出：[]

思路1：创建临时哑结点

删除操作，如果不创建哑结点，那么第一个数据结点（力扣题称为头结点）和其他数据结点需要区分开。
创建临时哑结点可以统一操作，不需要分类。
创建dummyHead，之后需要2个指针，cur指针指向正在被检查的结点。
prec指针指向被检查结点的前驱结点，因为删除当前结点后需要让前驱结点连上被删除结点的后继结点。
也就是prec->next = cur->next;
如果当前被检查结点的值等于val，就让prec->next = cur->next，并且释放当前被删除结点。
如果当前被被检查结点的值不等于val，就移动前驱指针prec到下一位。
不管当前结点需不需要被删除，都需要让当前指针cur指向下一个结点，也就是cur=prec->next;
如果cur=NULL，就说明检查结束。
注意：返回值是哑结点的下一位，因为原本头结点也可能被删除。

struct ListNode* removeElements(struct ListNode* head, int val){
	// 创建临时哑结点
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;						// 让哑结点连接头结点
    struct ListNode* prec = dummyHead;			// 让prec指针指向当前被检查结点的前驱结点
    struct ListNode* cur = prec->next;			// 让cur指针指向当前被检查结点
    while(cur)
    {
        if (cur->val == val)					// 如果当前被检查结点的值=val
        {
            prec->next = cur->next;				// 让其前驱结点连接其后继结点
            free(cur);							// 释放当前被检查结点
        }
        else
        {
            prec = prec->next;					// 如果当前结点和val不相等，就让prec前驱指针移动到下一位
        }
        cur = prec->next;						// 无论val和当前结点是否相等，都让cur往下移动一位
    }
    return dummyHead->next;						// 返回哑结点指向的下一个结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度：O(n)。需要遍历一遍当前链表。
• 空间复杂度：O(1)。需要一个哑结点的空间，2个指针空间prec和cur。

思路2：递归法

如果n(k+1)及其之后结点都已经移除完毕，只需要检查头结点。
如果头结点需要移除就返回头结点的下一个结点，否则返回头结点。

struct ListNode* removeElements(struct ListNode* head, int val){
    if (head == NULL)								// 如果head为空，就返回NULL
        return NULL;
    head->next = removeElements(head->next, val);	// 让头结点连接上已经被移除的链表
    return head->val == val ? head->next : head;	// 如果头结点需要删除，就返回head->next，否则返回头指针head
}
1
2
3
4
5
6

复杂度分析：

• 时间复杂度：O(n)。需要遍历一遍当前链表。
• 空间复杂度：O(n)。需要递归n次，每次需要O(1)的空间复杂度，n次则需要O(n)。
  
  

2.反转链表(206题)

问题描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例2：
输入：head = [1,2]
输出：[2,1]
示例3：
输入：head = []
输出：[]

思路1：利用头插法

创建一个临时的哑结点，初始化它的next域为NULL。
让cur指针指向当前需要被插入的结点。
每次将该结点插入到哑结点后面。
再让cur指针往后移动一位。
循环结束后，结点会逆序插入到哑结点后面，就完成了反转的工作。

struct ListNode* reverseList(struct ListNode* head){
	// 创建一个哑结点（第零个结点）
    struct ListNode dummyNode = {.next = NULL};
    // head指向当前未被插入的结点
    while (head)
    {
        struct ListNode* cur = head;		// cur指针指向当前被插入的结点
        head = head->next;					// 让head指向下一个结点
        cur->next = dummyNode.next;			// 让当前被插入的结点指向哑结点后的下一个结点
        dummyNode.next = cur;				// 让哑结点指向当前被插入的结点
    }
    return dummyNode.next;					// 返回哑结点指向的结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

• 时间复杂度：O(n)。需要遍历一遍当前链表。
• 空间复杂度：O(1)。需要一个哑结点dummyNode和一个cur指针的空间。

思路2：直接改变结点连接的顺序

假设链表为 1->2->3->NULL，直接改为NULL<-1<-2<-3即可。
算法思路：
让依次当前结点的next指针域指向它的前驱结点，就完成了反转。
需要3个指针:prec指向前驱结点，cur指向当前结点，succ指向后继结点。
因为让当前结点的next指针域从指向后继结点变成指向前驱结点。
这样做会让后继结点及其之后的结点丢失。
所以需要succ指针指向后继结点的地址，免得丢失。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;				// 定义指向当前结点的指针
    struct ListNode* prec = NULL;				// 定义指向前驱结点的指针
    while (cur)
    {
        struct ListNode* succ = cur->next;		// 定义指向后继结点的指针
        cur->next = prec;						// 让当前结点指向其前驱结点
        prec = cur;								// 让prec指针指向下一位
        cur = succ;								// 让cur指针指向下一位
    }
    return prec;								// 循环结束后，prec指向原本的最后一个结点，也就是反转后的第一个结点
}
1
2
3
4
5
6
7
8
9
10
11
12

复杂度分析：

• 时间复杂度：O(n)。需要遍历一遍当前链表。
• 空间复杂度：O(1)。需要三个指针prec、cur、succ的空间。

思路3：利用递归

递归的核心思路是：
假设第n+1个结点及其之后结点都反转了，只需要让第k个结点反转。
需要让nk+1->next = nk;
因为nk+1 = nk->next，所以需要让nk->next->next = nk;
接下来需要让nk->next指向NULL。
也就是让最后一个结点指向NULL。

struct ListNode* reverseList(struct ListNode* head){
	// 如果是空链表或者只有一个元素的链表，直接返回头结点
    if (head == NULL || head->next == NULL)		
        return head;
    // 假设head结点之后的所有结点都反转了
    struct ListNode* newHead = reverseList(head->next);	
    head->next->next = head;		// 让head结点的下一个结点指向head结点
    head->next = NULL;				// 再让head指向NULL，为了让头结点反转后指向NULL
    return newHead;  				// 返回反转后的第一个结点
}
1
2
3
4
5
6
7
8
9
10

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。需要n个栈，空间复杂度为O(n)。
  
  

3.链表的中间结点（876题）

问题描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路1：快慢指针

让fast指针一次移动2位，slow指针一次移动一位。
当fast指针移动到末尾时，slow指针就移动到中间。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    // fast == NULL是到偶数链表末尾，fast == NULL是到奇数链表末尾
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11

复杂度分析：

• 时间复杂度：O(n)。只需要执行n/2次的循环。
• 空间复杂度：O(1)。
  
  

4.回文链表（234题）

问题描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例1：
输入：head = [1,2,2,1]
输出：true
示例2：
输入：head = [1,2,3,2,1]
输出：true
示例3：
输入：head = [1,2]
输出：false

提示：
链表中节点数目大于零

思路1：反转链表后半段后，依次比较

核心逻辑为：
1.通过快慢指针找到链表的中间结点。
解释：用endOfFirstHalf函数找到链表前半段的最后一个结点(如果是5个元素就返回3，如果是4个元素就返回2）。
让快指针fast每次移动2位，慢指针每次移动一位，快指针移动到末尾，慢指针就找到中间结点了。
2.反转单链表的后半段。
解释：可以利用之前写过的reverseList函数，它可以将链表反转并返回新的头结点。
3.比较链表的前半段和后半段反转后的链表元素，判断是否为回文。
4.再次调用reverseList函数恢复原链表。
5.返回结果。
解释：如果查询到链表末尾，则返回true；否则返回false。

 struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;				// 定义指向当前结点的指针
    struct ListNode* prec = NULL;				// 定义指向前驱结点的指针
    while (cur)
    {
        struct ListNode* succ = cur->next;		// 定义指向后继结点的指针
        cur->next = prec;						// 让当前结点指向其前驱结点
        prec = cur;								// 让prec指针指向下一位
        cur = succ;								// 让cur指针指向下一位
    }
    return prec;								// 循环结束后，prec指向原本的最后一个结点，也就是反转后的第一个结点
}

struct ListNode* endOfFirstHalf(struct ListNode* head)
{
    struct ListNode* slow = head;		// 慢指针一次移动一位
    struct ListNode* fast = head;		// 快指针一次移动2位
    // fast->next == NULL，是奇数链表的情况，fast->next->next == NULL，是偶数链表的情况
    while (fast->next != NULL && fast->next->next != NULL) 
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;						// 循环结束后，slow指针到达前半段最后一个结点
}

bool isPalindrome(struct ListNode* head){
    // 找前半部分尾结点并且反转后半部分链表
    struct ListNode* firstHalfEnd = endOfFirstHalf(head);
    struct ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

    // 把链表前半部分和反转后的后半部分分为两部分，一一进行比较
    struct ListNode* list1 = head;
    struct ListNode* list2 = secondHalfStart;

    bool result = true;
    while (result && list2 != NULL)
    {
        if (list1->val != list2->val)
            result = false;
        list1 = list1->next;
        list2 = list2->next;
    }

    // 还原链表
    firstHalfEnd->next = reverseList(secondHalfStart);
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

复杂度分析：

• 时间复杂度：O(n)。大约需要2n次。
• 空间复杂度：O(1)。只是修改原本链表结点的指向，并没有创建新的链表，只需要常数项复杂度。
  
  

5.删除链表的倒数第 N 个结点（19题）

问题描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例2：
输入：head = [1], n = 1
输出：[]
示例3：
输入：head = [1,2], n = 2
输出：[1]
示例4：
输入：head = [1,2], n = 1
输出：[2]

提示：
链表中结点的数目为 sz
1 <= n <= sz

思路1：快慢指针

设置快慢双指针，让fast指针先走n步，再让slow指针和fast指针一起走。这样slow指针就比fast指针慢n步。
当fast指针走到末尾时，slow指针就刚好走到倒数第n个结点。
由于删除更需要的是被删除指针的前驱指针。
而且，如果没有哑结点，删除第一个结点的情况还得分类讨论。
所以，最好设置哑结点，同时让slow指针一开始指向哑结点，而fast指针一开始指向第一个数据结点（力扣的头节点）。
这样，当fast走到NULL时，slow指针指向被删结点的前驱结点。
之后只需要执行简单的删除操作即可（让被删除结点的前驱连接后继，并且释放被删除结点空间）。
返回的结果是哑结点的后继结点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
	// 让哑结点连接头节点
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* slow = dummyHead;			// slow指针初始化为哑结点
    struct ListNode* fast = head;				// fast指针初始化为头节点，比slow指针快一步
    // 先让快指针走n步
    while(n--)
    	fast = fast->next;
    // 再让slow和fast指针一起走，直到fast指针走到NULL
    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    struct ListNode* delete = slow->next;		// 记录被删除结点，也就是slow指针的下一个结点
    slow->next = delete->next;					// 让被删除结点的前驱连接后继，让它从链表中断开
    free(delete);								// 释放被删除结点空间
    return dummyHead->next;						// 返回哑结点的下一个结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。
  
  

6.合并两个有序链表(21题）

问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

思路1：迭代法

需要一个哑结点帮助我们返回连接好的链表，否则需要讨论表1和表2的第一个结点谁更小。
prec先指向哑结点。
让prec一直连接list1和list2中较小的当前结点，list1或者list2如果连接上一个元素，就后移一位。
不管连接上表1还是表2，prec每次都要后移一位，保证它一直在合并新表的末尾（这样遇到新的合并结点，才方便直接连接）。
如果其中一个表移动到末尾，就直接连接上另一个表剩余的元素。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	// 设置临时哑结点
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* prec = dummyHead;				// prec用来连接当前2个链表更小的结点
    while (list1 && list2)							
    {
        if (list1->val <= list2->val)				// 如果链表1的当前结点小于链表2的当前结点
        {
            prec->next = list1;						// 就让prec连接上链表1
            list1 = list1->next;					// 链表1的当前结点往后移动一位
        }
        else										// 如果链表2的当前结点小于链表1的当前结点
        {
            prec->next = list2;						// 就让prec连接上链表2
            list2 = list2->next;					// 链表2的当前结点往后移动一位
        }
        prec = prec->next;							// 只要连接一次，就让prec往后移动一位
    }
    prec->next = (list1 == NULL) ? list2 : list1;	// 如果其中一个链表移动到NULL，就让prec连接上另一个链表
    return dummyHead->next;							// 返回哑结点的下一个结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

复杂度分析：

• 时间复杂度：O(n+m)。 n和m是两个单链表各自的长度。
• 空间复杂度：O(1)。
  
  

思路2：递归法
只需要将两个结点的较小者和其他已经合并好的结点相连即可。
递归法只需要找到两个链表第一个结点的较小者，让它连接上其他已经合并好的结点。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
	// 如果其中一个表为空，就直接返回另一个表
   if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    // 只需要让最小的结点连接上其他已经被连接好的结点
    if (list1->val < list2->val)
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }
    else
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析：

• 时间复杂度：O(n+m)。 n和m是两个单链表各自的长度。
• 空间复杂度：O(n+m)。递归调用要调用n+m次。
  
  

7.分割链表(面试题 02.04.)

问题描述：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要保留每个分区中各节点的初始相对位置。
示例1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1,4,2], x = 2
输出：[1,2,4,2]

思路1：迭代法
思路很简单，定义两个头结点，一个用来连接小于x的结点，一个连接大于等于x的结点。
依次检查原单链表的每个结点，如果是小值，就连接上小值链表；如果是大值，就连接上大值链表。
每查询一个结点，让head指向下一个即将被检查的结点。
查询完毕后，各个结点已经分别存储到小值链表和大值链表中。
之后只需要先让大值链表的末尾指向NULL，再让小值链表末尾连接上大值链表的头结点。
就完成链表的分割了。
注意：要先让大值链表的末尾指向NULL，因为原链表可能一个大于等于x的值都没有，大值链表的哑结点还没有连接任何结点。
所以，需要先让大值链表的末尾指向NULL，才能让小值链表和大值链表连接。

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* dummyLess = (struct ListNode*)malloc(sizeof(struct ListNode));		// 新建哑结点存储小值结点
    struct ListNode* dummyLarge = (struct ListNode*)malloc(sizeof(struct ListNode));	// 新建哑结点存储大值结点
    struct ListNode* lessCur = dummyLess;							// lessCur指向小值链表的最后一个结点
    struct ListNode* largeCur = dummyLarge;							// largeCur指向大值链表的最后一个结点
    while (head != NULL)						
    {						
       if (head->val < x)											// 如果是小值，就连接上小值链表
       {
           lessCur->next = head;
           lessCur = lessCur->next;
       }
       else															// 如果是大值，就连接上大值链表
       {
           largeCur->next = head;
           largeCur = largeCur->next;
       }
       head = head->next;											// 连接完毕后，让head指向下一个待检查结点
    }
    largeCur->next = NULL;											// 先让大值链表的末尾指向NULL
    lessCur->next = dummyLarge->next;								// 再让小值链表末尾连接上大值链表的头
    return dummyLess->next;											// 返回小值链表的头结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。
  
  

8.相交链表（160题）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须保持其原始结构。
示例1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null。

思路1：双指针

这题的核心问题是，两个链表从头结点开始，找到相交结点需要的步数是不同的。
假设链表A的长度是a，链表B的长度是b，链表相交结点的数目是c。
虽然链表A和链表B头结点距离相交结点的步长不一样。
但是两段距离加起来的值是固定的。
可以从链表A遍历到链表B的相交结点，需要a+b-c。
也可以从链表B遍历到链表A的相交结点，需要b+a-c。
这时候两个链表都指向相交结点。
如果没有相交结点c=0，那么两个链表都同时指向NULL。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
	// 考虑特殊情况，如果有链表为空，就不可能有相交结点，直接返回NULL
    if (headA == NULL || headB == NULL)
        return NULL;
    struct ListNode* pA = headA;
    struct ListNode* pB = headB;
    // 如果链表A和链表B到达相交结点步长相同，那么走指定步长后,pA会等于pB
    // 如果步长不同，那么pA和pB会走到NULL，此时让pA从headB处继续往下走，pB从headA处继续往下走
    // 如果有相交结点，它们走相同步长后一定会相遇pA=pB
    // 如果没相交结点，pA和pB会同时遍历完链表A和B，同时走到NULL，此时也结束循环
    while(pA != pB)
    {
        pA = (pA == NULL) ? headB : pA->next;
        pB = (pB == NULL) ? headA : pB->next;
    }
    return pA;			// 如果有相交结点，结束循环后，pA=pB=相交结点，如果没有相交结点，pA=pB=NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度分析：

• 时间复杂度：O(n+m)。m和n分别是链表A和B的长度，最坏情况是遍历完链表A和B还是没相交。
• 空间复杂度：O(1)。
  
  

9.环形链表（141题）

问题描述：给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false。
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：

输入：head = [1], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例4：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路1：快慢指针

本题需要**「Floyd 判圈算法」**（又称龟兔赛跑算法）的基础。
可以查看我的另一篇博文：「Floyd 判圈算法」（又称龟兔赛跑算法）
设置一个快指针和慢指针指向头结点，快指针一次走2步，慢指针一次走一步。
按弗洛伊德判圈法，如果有环<=>快慢指针一定会在环内相遇。
所以，只需要检测快慢指针是否相遇，如果fast指针走到结尾，说明没环。如果快慢指针最终相遇，说明有环。

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    // 如果快指针走到末尾，结束循环
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)			// 如果快慢指针相遇，返回true
            return true;
    }
    return false;					// 如果跳出循环，说明fast到末尾，返回false
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。
  
  

10.环形链表 II（142题）

问题描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路1：快慢指针

先找到快慢指针第一次相遇的相遇点。
再让一个新的慢指针指向链表表头，原来的慢指针还是在相遇点，2个慢指针再次相遇时，该结点就是环的起点。

struct ListNode *detectCycle(struct ListNode *head) {
	// 如果链表是空表或者只有一个结点（且该节点的next不指向自身），直接返回false
     if (head == NULL || head->next == NULL)
        return false;
    // 快慢指针初始都指向头结点
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    do
    {
    	// 快指针每次移动2步，慢指针每次移动一步
        fast = fast->next->next;
        slow = slow->next;
        // 如果fast能走到末尾，说明没环，返回false
        if (fast == NULL || fast->next == NULL)
            return false;
    }
    while (fast != slow);				// 如果fast == slow，说明走到快慢指针相遇点
    struct ListNode* newSlow = head;	// 让新的慢指针指向链表头结点
    // 假如链表头结点也是环的起点，两个慢指针一开始就相遇，程序不需要进入循环，直接返回该结点
    // 假如链表头结点不是环的起点，两个慢指针首次相遇的结点，就是环的起点
    while (slow != newSlow)
    {
        slow = slow->next;
        newSlow = newSlow->next;
    }
    return slow;			// 首次相遇的结点位置，就是环的起点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

复杂度分析：

• 时间复杂度：O(n)。n为链表长度，快慢指针第一次相遇最多走n步，第二次2个慢指针相遇时最多再走n步。最多是O(n)+O(n) = O(n)
• 空间复杂度：O(1)。