相交链表~环形链表

前言

我们在解决环形链表问题之前呢，先做一道简单题做做铺垫；
环形链表的方法很简单，但是想要弄懂其中的原理，就不得不花费一番力气！！！😊😊😊接下咱就和大家一起来探讨一下这个问题！！！；

相交链表

题目描述：

➡️ 挑战链接 ⬅️
分析：

首先我们最容易想到的就是暴力破解，将一个链表的节点地址与另一个链表的每一个节点的地址进行比较，看看是否存在相同节点的情况，如果存在，则说明，两个链表存在相交；如果两个链表都遍历完了都没找到相同地址的节点，则说明两个链表无相交的情况出现；

时间复杂度：O（N^2）
空间复杂度：O(1)
代码实现：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
                 struct ListNode *curA=headA;
                 struct ListNode *curB=headB;
                 for(curA=headA;curA;curA=curA->next)
                 {
                     for(curB=headB;curB;curB=curB->next)
                     if(curB==curA)
                     return curA;
                 }
                 return NULL;
}
1
2
3
4
5
6
7
8
9
10
11

我们可以看到时间效率并不高，该算法还可以进一步改进；
方法2：

假设题目给定的两个链表一样长的话，我们就可以比较curA和curB的地址值，看看所指节点的地址是否一样，如果不一样则curA与curB同时向后走；
如果最后走到NULL都没找到的话，那么就说明两个链表不存在相交；相反如果存在curA等于curB则说明存在相交，直接返回curA或curB；
但是：
现在前提是我们不能保证两个链表是否一样长，则就需要我们去统计两个链表的长度了，然后让长链表先走长度差的绝对值步；这是就能保住curA和curB是一样长的了，就可以利用上面的思路了：
画图：

 size_t CountList(struct ListNode*head)
 {
     struct ListNode*cur=head;
     int len=0;
     while(cur)
     {
         len++;
         cur=cur->next;
     }
     return len;
 }
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
                 struct ListNode *cur1=headA;
                 struct ListNode *cur2=headB;
                 int len1=CountList(headA);
                 int len2=CountList(headB);
                 int k=0;
                 if(len2>len1)
                 {
                     k=len2-len1;
                     while(k--)
                     cur2=cur2->next;
                 }
                 else
                 {
                     k=len1-len2;
                     while(k--)
                     cur1=cur1->next;
                 }
                 while(cur2)
                 {
                     if(cur1!=cur2)
                     {
                         cur1=cur1->next;
                         cur2=cur2->next;
                     }
                     else
                     return cur1;
                 }
                 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

时间复杂度：O（N）；
空间复杂度：O（1）；

代码改良版：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
          struct ListNode *curA=headA;
          struct ListNode *curB=headB;
          int lenA=0;
          int lenB=0;
          //1、先判断一下每个链表的最后一个节点是否相等，如果最后一个节点都不想等，说明两个链表一定没有相交；反之，则一定相交了；
          while(curA->next)
          {
              curA=curA->next;
              lenA++;
          }
          while(curB->next)
          {
              curB=curB->next;
              lenB++;
          }
          if(curB!=curA)//两链表最后一节点比较
          return NULL;
          //以上没有相交的链表都没拦截于此
          //接下来就是处理一定相交的链表，还是上面代码的思路；
          struct ListNode *LongList=headA;
          struct ListNode *ShortList=headB;
          if(lenB>lenA)
          {
              LongList=headB;
              ShortList=headA;
          }
           int gap=abs(lenB-lenA);//两链表的节点数目差值
           //先让长链表先走gap步
           while(gap--)
           {
               LongList=LongList->next;
           }
           //两个链表保持一致长了
           while(LongList)
           {
               if(LongList==ShortList)
               break;
               LongList=LongList->next;
               ShortList=ShortList->next;
           }
          return ShortList;
} 
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

环形链表Ⅰ

前面铺垫做完了，我们再来慢慢进入正题：
题目描述：

➡️ 挑战链接 ⬅️
分析：

首先解决这道题目的方法就是快慢指针，fast指针每次走2步，slow指针每次走1步；
如果有环的话，fast指针一定会等于slow指针（why？我们下文解释）；
如果没环的话，fast最后一定是等于NULL或者fast->next==NULL；

偶数节点，无环情况，结束条件；

奇数节点，无环情况，结束条件

时间复杂度：O（N）
空间复杂度：O（1）
代码实现：

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(slow==fast)//说明带环
             return true;
         }
         return false;
}
1
2
3
4
5
6
7
8
9
10
11
12

代码和思路就是这么简洁
下面我们来解释一下：为什么快指针每次走两步，慢指针走一步可以？快指针可不可以每次走3步？

假设链表带环
首先我们清楚一定是快指针先进入圆环，对吧！
其次呢，当我slow指针刚好在圆环进入点的时候，fast指针也存在与圆环中的某个位置，如图：

同时呢，我们假设fast和slow指针的相对步长呢为N步（顺时针方向的步长），现在我们fast指针是每次走两步，slow指针是每次走一步，那么我们就走呗：

同时我们可以知道fast和slow指针没变换一次，他们之间的距离就会减少1步；
why？
我们可以这样理解，假设只有fast动，那么fast和slow之间的距离是不是就是N-2；
但是现在加上slow动的距离，fast和slow之间的距离是不是又被拉大了，变为N-2+1，即N-1；
后面以此类推……
那么fast与slow之间的距离变化就是：
N
N-1
N-2
N-3
……
0//
fast和slow之间距离最后会减小为0；
当N==0了就说明fast与slow并肩同行了，也就是说fast==slow了；
这样解释了，为什么fast每次走2步，slow每次走1步，最会一定会在环里面并肩；
那么我们再来看看，fast每次走3步，slow每次走1步行不行嘞？
还是刚才的思路，fast与slow的初始距离为N：

那么下一次的距离就变为了N-2；
假设只有fast动，距离就是N-3，加上slow移动距离，使得slow与fast之间距离变大，N-3+1，即N-2；
后面依次类推……
N的变化规律：
N
N-2
N-4
……
假设N是偶数的话，那么N最后一定会减为0，那么fast一定能与slow并肩，也就一定能有fast==slow；
假设N是奇数的话，那么N最后一定会为-1，这个-1代表什么意思？
就是说fast与slow擦肩而过，fast刚好领先slow一步，这时我们设圆环周长为C，
那么fast和slow之间的距离（fast到slow，顺时针）就为C-1；

这不有回到上一层？
令T=C-1
T的变化：
T
T-2
T-4
……
假设T为偶数的话，那么slow与fast指针一定能并肩；
假设T为奇数的话，那么fast与slow永远不可能并肩了；
why？
T都为奇数了，那么是不是最后又会回到T=-1的时候？是不是又回到了上图表示的情形，fast与slow之间的距离又是T（C-1）然后就这样不断循环，所以fast永远不可能并肩；
这也就是我们为什么会让fast走2步，slow走1步的原因；（当然只要fast与slow之间的速度差等于1，理论上来说都是可以并肩的）
————————————————————————————————————————————————
同时，如果我们悬着fast每次走2步，slow每次走一步的情况的话，slow和fast最多在一圈内完成并肩；
我们再来证明这个理论：

好了，现在我们知道了这些原理和解释，我们来给环形链表加点难度；

环形链表Ⅱ

题目描述：

➡️挑战链接⬅️
分析:
通过上面的题我们知道了如何判断一个链表是不是环形链表,那么我们的对于上面的码,我们可以稍加处理:

struct ListNode *detectCycle(struct ListNode *head) {
     struct ListNode *fast=head;
       struct ListNode *slow=head;
         while(fast&&fast->next)
         {
             fast=fast->next->next;
             slow=slow->next;
             if(slow==fast)//说明带环
             {
             //核心部分
             }
         }
         return NULL;//链表无环
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这时问题就变为了,如何计算带环链表的进环入口,
首先我先说结论;

我们通过上文的证明,我们知道如果fast每次走2步,slow每次走一步,一定会在环内相遇,
那么我们吧相遇点记为meet,然后将链表头节点记为plist,然后让plist和meet每次都走1步的速度往后走,最后一定会存在meet等于plist的情况,那么那个相等的点就是入口点!!;
代码实现:

struct ListNode *detectCycle(struct ListNode *head) {
     struct ListNode *fast=head;
       struct ListNode *slow=head;
         while(fast&&fast->next)
         {
             fast=fast->next->next;
             slow=slow->next;
             if(slow==fast)//说明带环
             {
             //核心部分
             struct ListNode *meet=slow;
             struct ListNode *plist=head;
             while(plist!=meet)
             {
                 meet=meet->next;
                 plist=plist->next;
             }
             return plist;
             }
         }
         return NULL;//链表无环
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我们现在来解释一下,为什么meet与plist为什么一定会相遇,并且一定相遇与入口点:

当然前面我们证明了,slow与fast一定在一圈以内完成并肩,因此slow的距离是L+N;

如果上面寻找入口节点的方法不明白,还有个更简单的办法,就是将meet位置节点剪掉,同时将slow->next置空,那么环形链表是不是就变为了相交链表,而入口点不就是第一个相交点嘛:
于是我们当一把CV工程师:
代码实现:

 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
          struct ListNode *curA=headA;
          struct ListNode *curB=headB;
          int lenA=0;
          int lenB=0;
          while(curA->next)
          {
              curA=curA->next;
              lenA++;
          }
          while(curB->next)
          {
              curB=curB->next;
              lenB++;
          }
          if(curB!=curA)
          return NULL;
          struct ListNode *LongList=headA;
          struct ListNode *ShortList=headB;
          if(lenB>lenA)
          {
              LongList=headB;
              ShortList=headA;
          }
           int gap=abs(lenB-lenA);
           while(gap--)
           {
               LongList=LongList->next;
           }
           while(LongList)
           {
               if(LongList==ShortList)
               break;
               LongList=LongList->next;
               ShortList=ShortList->next;
           }
          return ShortList;
} 
struct ListNode *detectCycle(struct ListNode *head) {
     struct ListNode *fast=head;
       struct ListNode *slow=head;
         while(fast&&fast->next)
         {
             fast=fast->next->next;
             slow=slow->next;
             if(slow==fast)//说明带环
             {
             //核心部分
             struct ListNode *plist=head;
             struct ListNode *meet=slow->next;
             slow->next=NULL;
                 return getIntersectionNode(plist,meet);
             }
         }
         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

时间复杂度:O(N)
空间复杂度:O(1)