[LeetCode] Linked List Cycle II 链表环起始位置

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Hide Tags

 Linked List Two Pointers

 

 

---

   开始犯二了一点，使用了node 的val 作为判断，其实是根据内存判断。找出链表环的起始位置，这个画一下慢慢找下规律便可以：

思路：

1. 使用快慢指针，慢指针每次前进一步，快指针每次两步
2. 如果快慢指针相遇了，那么将快指针从标记带链表头，改为每次前进一步
3. 当快慢指针再次相遇便是环起始位置。

这样的实现，时间很快O(n)，而且空间O(1)

#include <iostream>
using namespace std;
/**
 * 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) {
        if(head==NULL)  return NULL;
        ListNode * fast=head,*slow=head;
        while(1){
            if(fast->next!=NULL)    fast=fast->next;
            else return NULL;
            if(fast->next!=NULL)    fast=fast->next;
            else return NULL;
            slow=slow->next;
            if(fast==slow) break;
        }
        fast=head;
        while(1){
            if(fast==slow) return slow;
            fast=fast->next;
            slow=slow->next;
        }
        return NULL;
    }
};

int main()
{
    ListNode node1(1),node2(2),node3(3),node4(4),node5(5);
    node1.next=&node2;
    node2.next=&node3;
    node3.next=&node4;
    node4.next=&node5;
    node5.next=&node1;
    Solution sol;
    ListNode *ret = sol.detectCycle(&node1);
    if(ret==NULL)   cout<<"NULL"<<endl;
    else cout<<ret->val<<endl;
    return 0;
}