链表的带环问题

带环问题，是链表众多问题中一类经典的问题，下面我们就来深度剖析一下链表的带环问题。

一，判断链表是否带环

题目通常会 给你头节点的指针，让你判断这个链表是否带环。
注： 结点自己指向自己也是带环链表。

这道题的思路是使用快慢指针来解决的，定义一个指针slow和一个指针fast，快指针每次走两步，慢指针每次走一步，当快慢指针指向同一个结点的时候证明链表是带环链表。

bool hasCycle(struct ListNode *head) {
    struct ListNode* fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

看上去，代码很简单，但我今天讲的是这个方法的原理。
首先，我们先简化一下带环链表的模型。

前面的直线表示没有进入环之前的结点，圆圈表示环上的结点。
由于，快指针的速度是慢指针的二倍，那么就代表fast指针刚进入环的时候slow指针，走到了直线的中点，也就是下图这样。

当我们的slow指针进入环的时候fast指针已经走了K圈了（K是大于等于0的），如下图所示：

此时，就转换成了一个追及问题，fast的速度是slow的二倍，slow每次走一个结点，fast与slow相差N步，那么fast相对于slow的速度就是1，也就是说fast每走一次，fast与slow之间的距离就会减少一步，那么，fast走2N步，slow走N步时，两个指针就会相遇。

提升： 肯定会有人继续追问？为何快指针每次走两步呢？那么走3步行不行呢？为什么快指针走2步就一定会相遇呢？
下面我们来讨论一下，走fast指针一次走3步行不行：

首先，无论fast指针走几步最终fast与slow指针都会进入到环中，我们假设当slow指针刚进入环的时候与fast指针相差N步，由于此次fast指针每次走3步，也就意味着fast相对于slow的速度是2，就是说fast每走一次与slow的差距就会减少两步。

N N-2 N-4 。。。。。。 2 0
N N-2 N-4 。。。。。。3 1 -1

会出现上述的两种情况，究竟最终会相差3步呢？还是相差两步呢？这是未知的所以我们得分情况考虑，第一种情况fast与slow最终相差0步，证明fast与slow可以相遇。
但，第二种情况，最终fast与slow相差-1步，就是说fast反超slow了，此时进入到新一轮的追击问题了，他们相差的步数为（假设圆圈的周长为C）C-1。

如果C是一个奇数那么C-1就为偶数，那么最终fast就会与slow相遇。
如果C是一个偶数那么C-1就为奇数，就会导致fast永远不会与slow相遇，是一个死循环。

所以fast每次走两步，slow一次走一步，一定是可以相遇的，因为相对速度为1，每走一次距离就会减少1，最终相遇，而fast一次走3步，就会遇到fast与slow错过的问题。
同样fast一次走4 5 6 7步等等，都会出现这样的问题。
总结：只有fast相对于slow的速度为1的时候才能确保fast与slow会在环中相遇。

二，求入环结点

在将求入环结点的问题之前，先将一个求链表相交的问题。为求入环结点做铺垫。

1，链表相交问题

输入两个链表，返回他们第一个相交的结点，没有就返回NULL；

在这，我也提供一种类似快慢指针的解法，假如说A与B链表的长度是相等的，那么他们相等的第一个结点就是它们相交的结点。
所以，我们就要构造出AB长度相同，首先我们可以计算A和B的长度，然后让长的链表先走差距步，在一起走（此时就相当于AB是等长的）

举个例子说：例如上图中A的长度是5，而B的长度是6，那么我们就想让B走差距不也就是1步，然后A和B在同时走，他们相遇的第一个结点就是焦点。
此外，我们还可以在第一次遍历A与B的时候判断一下他们有无相交的可能：因为两个链表相交那么他们的尾结点一定是相同的。如果不相同那么直接返回NULL；

下面看代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(!headA||!headB)
    {
        return NULL;
    }
    struct ListNode* curA=headA,*curB=headB;
    int lenA=0,lenB=0;
    //找到尾结点，判断是否相交
    while(curA->next)
    {
        lenA++;
        curA=curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB=curB->next;
    }
    if(curB!=curA)
    {
        return NULL;
    }
    //找到较长的链表
    int k=abs(lenA-lenB);
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    if(lenB>lenA)
    {
        longlist=headB;
        shortlist=headA;
    }
    //先让较长的链表先走k步
    while(k--)
    {
        longlist=longlist->next;
    }
    //一起走，第一个相同的结点就是
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}
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

2，法一

此时，我们正式来讲求入环结点的问题：
第一种解法，要将寻找入环节点的问题转化为-寻找交点的问题，

由于我们在上面讲到，如果一个链表带环，那么快慢指针一定会在环上相遇，
当slow指针与fast指针相遇时，我们新创建一个指针叫meet指向此时的fast与slow，
先将meet的下一个位置记为newhead
然后将meet的next指针置为NULL；

此时，入环节点不久变成，头指针为head与头指针为newhead的链表求交点的问题了嘛？

代码如下：

 struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB)
 {
     struct ListNode* curA=headA;
     struct ListNode* curB=headB;
     int lenA=0,lenB=0;
     while(curA->next)
     {
         lenA++;
         curA=curA->next;
     }
     while(curB->next)
     {
         lenB++;
         curB=curB->next;
     }
     if(curB!=curA)
     {
         return NULL;
     }
     //确定先走的步数
     int k=abs(lenA-lenB);
     struct ListNode* longlist=headA;
     struct ListNode* shortlist=headB;
     if(lenB>lenA)
     {
         longlist=headB;
         shortlist=headA;
     }
     //先走k步
     while(k--)
     {
         longlist=longlist->next;
     }
     while(longlist!=shortlist)
     {
         longlist=longlist->next;
         shortlist=shortlist->next;
     }
     return longlist;
 }
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow,*fast;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            struct ListNode* meet=fast;
            struct ListNode* next=meet->next;
            meet->next=NULL;
            return getIntersectionNode(head,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
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

3，法二

方法二：也是在fast与slow的交点开始，创建一个指针变量newhead指向fast与slow的交点，然后同时遍历head与newhead，他们第一个相同的位置就为入环结点

下面看代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            struct ListNode* newhead=fast;
            while(head!=newhead)
            {
                head=head->next;
                newhead=newhead->next;
            }
            return head;
        }
    }
    return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这种方法代码很简单，但是要事先论证为何会在入环点相遇。
证明： 由于fast的速度是slow的二倍，所以在相交时，fast走过的路程是slow走过路程的二倍。

我们假设直线的长度为L，圆圈的周长为C。
slow路程：L+N
fast路程：L+KC+N（K大于等于0）
建立等式关系：
2 （L+N）=L+N+KC
所以 L=KC-N
也就是head从头开始走，newhead从交点开始走，一定会在入环点相遇。

感谢阅读，欢迎指正。