活动地址：CSDN21天学习挑战赛

快慢指针巧解带环单链表问题

Leetcode141——环形链表

题目描述

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

链接：Leetcode141

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围是 [0, 104]
• -105 <= Node.val <= 105
• pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

核心代码模式

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    
}
1
2
3
4
5
6
7
8
9
10

思路分析与实现代码（C语言）

带环链表千万不要直接遍历，你都不知道啥时候就进环了，更别说什么链表长度了。
我们这里运用快慢指针来求解。大体思路如下：

我们定义快指针fast和慢指针slow，让快指针先走，一次走两步，慢指针后走，一次走一步（注意，这里的“步”是以结点为单位的形象说法）。我们假设有一个链表，它的前一部分是线性的，后一部分是环状的。
当慢指针才走到线性部分的中点时，快指针已经走到了线性部分与环状部分的交汇点了。

让两个指针继续走下去，当慢指针刚进环时，快指针已经在环状结构中走了一段路程了，具体走到哪里不确定，是走了不到一圈还是已经走了n圈，这些都不确定，我们这里先给它任意安排一个位置。

好了，要是再走下去，你觉得会怎样？直觉告诉你，它们两个最终总会相遇是吧，为什么呢？
首先，快指针和慢指针速度有差别，相对速度为1步/次，如果是在完全线性的链表中，slow不可能追得上fast（这算是高中物理常识了），而在环状循环结构中，原本在追赶fast的slow现在貌似也在被fast追赶，追赶是相对的，由于fast速度更快，我们这里认为在环状结构中是fast在追赶slow，那么fast追上slow只是时间问题。
这样设计的话fast一定能在环状结构中追上slow吗？如果能，如何简要地证明呢？（下面的证明拓展到了通用）
证明：
如图，设slow刚入环的时候两指针相差距离为N（这里以顺时针方向为正方向）。

fast和slow的速度差是1步/次，而且是fast更快，所以随着时间推移，两指针的距离差在不断缩小，那缩小就意味着一定会相遇吗？不一定。我们看看两指针的距离差的变化：N、N-1、N-2…2、1、0，发现在fast一次走两步、slow一次走一步的情况下，它们之间的距离差最终会缩小为0即两指针相遇，实际上，它们的距离差是否会变化为0和速度差有很大关系。
无论快指针设定一次走几步、慢指针一次走几步，都能由一个简单的公式来判断是不是一定能相遇。
设每时刻的距离差为x，两指针速度差为v，所经历时间为t（这里一直提到的时间不是实际时间，而是代码操作次数），沿用前面设定的初始距离差N，则有
x = N - vt
欲使x变为0，则需N - vt为0，而t是由情况而增长的自然数，故要使N = vt，即v = N / t，而v为整数，所以要求N为v的倍数。
由此可知，只要让两指针的速度差v是初始距离差N的约数就一定能使两指针的距离差x最终变为0，两指针相遇，如果不是倍数约数的关系的话，就不一定能相遇。
所有正整数都是1的倍数，所以v = 1一定能使x最终为0，也就说明快指针一次走两步、慢指针一次走一步，到最后一定能相遇。

结论:
通过上述的说明，我们发现，链表中只要是存在环状结构，那么fast一定会和slow相遇，那么反过来说，要是fast和slow能相遇，那么就一定存在环状结构（因为线性情况下不可能相遇）。

代码实现

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)
            return true;
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Leetcode142——环形链表Ⅱ

题目描述

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

链接：Leetcode142

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？


核心代码模式

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    
}
1
2
3
4
5
6
7
8
9
10

思路分析与代码实现（C语言）

1.公式法

这个方法主要靠一个推导出来的公式，能想到的话代码就很简单了，不过确实不好想到。还是用快慢指针，参考上一题思路。

推导过程：
如图，设链表中线性部分长度为L，入环口和快慢指针相遇点的距离为X，环的长度为C。

则slow走过的路程为L+X，由于fast走过的路程是它的两倍，所以fast走过了2(L+X)。
实际上，fast在slow指针走到入环口之前可能已经在环中走过了n圈加C-X的距离，slow刚到入环口时，如图

此时slow再走X距离直到两指针相遇，fast就走了2X，所以fast走过的总路程还可以表示为L+nC+(C-X)+2X即L+nC+C+X。
所以有如下方程：
2(L+X) = L+nC+C+X
L+X = nC+C
L =nC+C-X
好了，那得到的这个等式有什么用呢？

结论：
一个指针从链表头部出发，另一个指针从二倍率（指速度差为1）快慢指针相遇点出发，它们到入环口的距离相同，也就是说它们最终相遇位置就是入环口即链表开始入环的第一个结点。

代码实现

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* meet = NULL;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            meet = slow;
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
        }
    }

    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.转换相交法

上面的那个思路实在不好想到，这里给出一个比较好想的思路，虽然代码繁琐些。
你看啊，带环链表线性部分和环状部分是相交的，一定会有交点对吧，那可不可以把环给“切开”，一刀两断，直接就变成“Y”字形相交链表，原来的入环口就变成了相交链表的第一个交点，问题不就转换成了求相交链表第一个交点的问题了嘛。不过啊，这能随便找个地儿切环吗？这肯定不能啊，你都不知道自己进没进环，就是说环的位置不好确定，那咋整？用快慢指针找相遇点呗，把相遇点作为分界呗。
相交链表有原题的，链接：Leetcode160 ，这里就不赘述了。
要注意的是，由于题目说了不能修改指针，所以我们再切断环找到入环口后最好把环再给拼接回去。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
     if(headA == NULL && headB == NULL)
         return NULL;

    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;

    int cntA = 1;
    int cntB = 1;

    while(tailA->next)
    {
        tailA = tailA->next;
        cntA++;
    }

    while(tailB->next)
    {
        tailB = tailB->next;
        cntB++;
    }

    if(tailA != tailB)
        return NULL;

    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;

    if(cntA < cntB)
    {
        longList = headB;
        shortList = headA;
    }

    int gap = abs(cntA - cntB);

    while(gap--)
    {
        longList = longList->next;
    }

    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }

    return longList;

}

 
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* meet = NULL;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            meet = slow;
            struct ListNode* newHead = meet->next;
            meet->next = NULL;
            struct ListNode* entryNode = getIntersectionNode(head, newHead);
            meet->next = newHead;
            return entryNode;
        }
    }
    return NULL;
    
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76