剑指offer:链表中环的入口结点

小鱼儿 2022-04-10 09:23 171阅读 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步； 此时正好在环的开始节点相遇。**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    
    /*
    //                  a        b 
    //         start ------->-------->meeting
    //                      |         |
    //                      <----------
    //                           c
    //         假设快指针和慢指针在第k步相遇
    //         k=a+b+r1(b+c) slow runs r1 cycles
    //         2k=a+b+r2(b+c) fast runs r2 cycles
    //         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 which means when slow moves (n-1) cycles and c, start moves 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) {
                    isCycle = true;
                    break;
                }
            }
            
            if(!isCycle)
                return NULL;
    
            while(fast != head) {
                head = head->next;
                fast = fast->next;
            }
            
            return head;
        }
    };