leetcode142. 环形链表 II

哈希

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        ListNode* cur=head;
        while(cur){
            if(set.count(cur))
            return cur;
            set.insert(cur);
            cur=cur->next;
        }
        return nullptr;
    }
};

双指针

任意时刻，fast 指针走过的距离都为slow 指针的2倍。因此，我们有
a=c+(n-1)(b+c)=2(a+b)⟹a=c+(n−1)(b+c)。
有了a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。即slow走到入环点时，就是a的距离。

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