带环链表的相关知识点

如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了体现给定链表中的环，评测系统内部使用整数 pos 来体现链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际环境。
  1.判断是否有环

方法:快慢指针追击
fast每次走两步,slow每次走一步。如果fast（或fast->next）能指向NULL,则阐明无环;如果fast追击到==slow,则阐明有环。

1. /**
2. * struct ListNode()
3. * {
4. *         int val;
5. *         struct ListNode* next;
6. * };
7. **/
8. bool hasCycle(struct ListNode *head){
9.         struct ListNode* slow = head,*fast = head;
10.         while(fast && fast->next)
11.         {
12.                 slow = slow->next;
13.                 fast = fast->next->next;
15.                 if(slow == fast)
16.                         return true;
17.         }
18.         return false;
19. }

复制代码

证实：
问题1：为什么一定会相遇，有没有可能错过，然后永远追不上？

slow走一步，fast走两步，假设从slow入环后最开始两个指针相差的距离为n，随着fast的追赶距离逐步减小，末了为0阐明相遇。
问题2：slow一次走一步，fast一次走两步，fast可不可以走3步、4步…?

• 假设fast走3步，那么两个指针之间距离的变化趋势为n、n-2…，即必要通过判断n的奇偶性来确定，因此就目前而言，fast走别的步数不一定，有可能错过。
  
• 在这个例子中，n为偶数则相遇，n为奇数则错过，开始了下一轮循环，这时fast和slow距离相称于-1，假设周长为C，如果C-1为偶数则相遇，为奇数则永远追不上。
  fast和slow可能错过吗？
  证实：
  假设fast一次走3步，slow到达环时，fast已经走了x圈并再走了C-N。
  
  
  
  可得：
  3 * L = L+x * C+C-N
  2 * L = (x+1) * C-N
  综上可得：只有当n为奇数、C为偶数时fast才会永远追不上，但从这个等式来看，这种环境不存在，所以不存在追不上的环境。
  

2.寻找入环节点

方法：
2.1 两个节点，一个从head走，另一个从meet走
证实：

假设fast一次走两步。
2 * slow = fast
2 * (L+N) = L+x * C+N
L+N = x * C
L = x * C-N
L = (x-1) * C+(C-N)

1. struct ListNode* detectCycle(struct ListNode* head){
2.         struct ListNode* slow = head,*fast = head;
3.         while(fast && fast->next)
4.         {
5.                 slow = slow-next;
6.                 fast = fast->next->next;
8.                 //相遇
9.                 if(slow == fast)
10.                 {
11.                         struct ListNode* meet = slow;
12.                         while(meet != head)
13.                         {
14.                                 meet = meet->next;
15.                                 head = head->next;
16.                         }
17.                         return meet;
18.                 }
19.         }
20.         return NULL;
21. }

复制代码

2.2 将相遇节点的下一个节点置空，这样就转换为了求链表相交节点的问题

1. struct ListNode* detectCycle(struct ListNode* head){
2.         struct ListNode* slow = head,*fast = head;
3.         while(fast && fast->next)
4.         {
5.                 slow = slow->next;
6.                 fast = fast->next;
8.                 //相遇
9.                 if(slow == fast)
10.                 {
11.                         struct ListNode* meet = slow;
12.                         struct ListNode* newhead = meet->next;
13.                         meet->next = NULL;
15.                         return getIntersectionNode(head,newhead);
16.                 }
17.         }
18.         return NULL;
19. }

复制代码

补充：相交链表

两个链表的next指向同一个节点，判断两个尾指针是否相等（地址判断）。
思路1：A链表中的节点依次与B全部节点比力，相等即交点。
O(N^2)/O(M * N)，时间复杂度过大
思路2：使长链表与短链表长度一样，一起遍历比力，相等即交点。
时间复杂度为O(N)

1. struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB){
2.         struct ListNode* curA = headA,*curB = headB;
3.         int lenA = 1,lenB = 1;//当下一个节点为空时不进入循环，尾结点没有被算入长度
4.         while(curA->next)
5.         {
6.                 curA = curA->next;
7.                 ++lenA;
8.         }
9.         while(curB->next)
10.         {
11.                 curB = curB->next;
12.                 ++lenB;
13.         }
14.         //尾结点不相等就是不相交
15.         if(curA != curB)
16.         {
17.                 return NULL;
18.         }
19.         //长的先走差距步，再同时走，第一个相等就是交点
20.         //假设法
21.         int gap = abs(lenA-lenB);
22.         struct ListNode* longList = headA,*shortList = headB;
23.         if(lenB > lenA)//如果上述长短情况不符合则互换
24.         {
25.                 longList = headB;
26.                 shortList = headA;
27.         }
28.         while(gap--)
29.         {
30.                 longList = longList->next;
31.         }
32.         while(longList != shortList)
33.         {
34.                 longList = longList->next;
35.                 shortList = shortList->next;
36.         }
37.         return shortList;
38. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。