142. Linked List Cycle II.md

142. Linked List Cycle II

思路

判断一个链表是否有环并且找到环的开始位置.要求空间复杂度O(1)

思路一

和之前普通判断是否有环的思路是类似的, 依然是使用两个指针, 一快一慢, 快指针每次走两步慢指针每次走一步. 若两指针相遇了肯定有环否则遇到NULL则没环. 那么当有环时如何判断环的起始位置呢?

我们假设两指针走了k次后相遇, 链表头到环开始节点距离为S(即所求), 从环开始节点到两指针相遇节点距离为M, 环的长度为R; 则我们有:

• 快指针走的路程2k = S + M + xR, 其中x是快指针走过环的整圈数;
• 慢指针走的路程为k = S + M + yR, 其中y是慢指针走过环的整圈数;

则我们有S + M + xR = 2(S + M + yR), 化简得S + M = (x-2y)R. 即我们得到了一个重要的结论: 从表头到相遇节点的距离等于环长的整数倍. 那么我们如果使用两个指针分别从表头和相遇节点开始向后每次走一步, 那么这两个节点走了S步后一定会相遇, 这个相遇节点即所求.

思路二

还有个更好理解的思路，假设环长为R，如果去掉尾节点指向入口节点的指针，即形成单链表，则我们要求的就是这个单链表的倒数第R个节点，所以我们像求倒数第R个节点那样求入口节点：定义两个指针p1和p2，让p1先向后移动R步，然后两个指针再每次一步地向后移动，二者将在入口节点相遇。

问题是如何求得环长R呢，也很简单，先还是用快慢指针，两指针将在环内部相遇，记录好这个相遇节点，然后再用慢指针继续向后移动并记录移动次数，最后回到相遇节点时这个次数就是环长R。

C++

思路一

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow=head;
        while(fast && fast -> next){
            fast = fast -> next -> next;
            slow = slow -> next;
            if(fast == slow) break;
        }
        if(!fast || !(fast -> next)) return NULL;
        
        fast = head;
        while(fast != slow){
            fast = fast -> next;
            slow = slow -> next;
        }
        
        return fast;
    }
};

思路二

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head, *tmp = NULL;
        while(fast && fast -> next){
            slow = slow -> next;
            fast = fast -> next -> next;
            if(slow == fast) break;
        }
        if(!fast || !(fast -> next)) return NULL;
        
        int R = 1; // 环长度
        tmp = slow; slow = slow -> next;
        while(slow != tmp){
            R++;
            slow = slow -> next;
        }
        
        ListNode *p1 = head, *p2 = head;
        while(R--) p1 = p1 -> next;
        while(p1 != p2){
            p1 = p1 -> next;
            p2 = p2 -> next;
        }
        return p1;
    }
};