LeetCode 142.Linked List Cycle II (环形链表 II) 详解

约定不等于承诺〃 2022-05-08 13:22 160阅读 0赞

题目描述：

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 `null`。

**说明：**不允许修改给定的链表。

**进阶：**  
你是否可以不用额外空间解决此题？

AC C++ Solution:

解题思路：

还是使用两个指针，一个fast，每次移动两步；一个slow，每次移动一步。

a b  
start ------->-------->meeting (k)  
<----------  
c

start是链表开始的位置，假设第一次相遇是在第k步。

k=a+b+r1(b+c) slow指针在环中循环了r1圈

2k=a+b+r2(b+c) fast指针在环中循环了r2圈

**2k=a+b+r2(b+c)=2a+2b+2r1(b+c)**

(b+c)(r2-2r1)=a+b => (b+c)n=a+b

得到：

**a=(n-1)b+nc=(n-1)(b+c)+c ：**

**这意味着一个指针(假设slow)从相遇节点k开始在环中移动，一个指针(假设head)从start开始移动；**

**当slow移动n-1个周期 + c步时，head移动a步； 此时正好在环的开始节点相遇。**

代码如下：

class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(head == NULL || head->next == NULL)   return NULL;
            ListNode* fast = head;
            ListNode* slow = head;
            bool isCycle = false;
            
            while(fast != NULL && fast->next != NULL) {
                fast = fast->next->next;
                slow = slow->next;
                
                if(fast == slow) {        //此时fast和slow处于第一次相遇节点处
                    isCycle = true;
                    break;
                }
            }
            
            if(!isCycle)
                return NULL;
    
            while(slow != head) {        //head从链表头移动，slow从开始位置移动
                head = head->next;
                slow = slow->next;
            }
            
            return head;
        }
    };