20191219leecode142快慢指针学习

1 题目

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

2 hash法与快慢指针法

快慢指针法有意思的推导：

x：link起点到入环点距离

y: 入环点到相遇点距离

c：circle的长度

相遇时候，慢指针走了x+n1 c + y （n1假设走了n1圈），快指针走了2倍(x+ n1c+y)

快指针比慢指针多走的路程一定是环长度的整数倍，有2(x+ n1c+y) - (x+ n1c+y) = n2 c

所以又x + y = (n2 - n1) c

可以相遇时快指针从起点再走（1倍速），慢指针也走，则相遇点就是入环点。

//  leecode 142 circle link detection

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// save elem to set, time O(n) space O(n)
ListNode *detectCycle(ListNode *head) {
    ListNode* p = head;
    set<ListNode*> elem_set;
    while(p){
        if (elem_set.find(p) != elem_set.end()) {
            return p;
        }
        elem_set.insert(p);//O(logN)
        p = p->next;
    }
    return NULL;
}

//fast and slow pointer
ListNode *detectCycle1(ListNode *head){
    ListNode *slow,*fast;
    slow = head;
    fast = head;
    while (slow!=NULL && fast->next!=NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            //fast pointer go from and start of the link
            fast = head;
            while (fast != slow) {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;//now both pointer is in the start of the citcle
            break;
        }
    }
    return NULL;
}



int main(){
    //input
    ListNode* res;
    ListNode *dummyhead,*head,*temp0,*temp1;
    dummyhead = new ListNode(-1);
    head = new ListNode(1);
    dummyhead ->next = head;
    temp0 = new ListNode(2);
    head->next = temp0;
    temp1 = new ListNode(4);
    temp0->next = temp1;
    temp1->next = temp0;
    
    //algorithm
    //res = detectCycle(head);
    res = detectCycle1(head);
    if (res == NULL) {
        cout<<"no circle"<<endl;
    }
    else cout<<res->val<<endl;
    return 0;
}