[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 作为判断，其实是根据内存判断。找出链表环的起始位置，这个画一下慢慢找下规律便可以：

思路：

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

这样的实现，时间很快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(){

            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(){

            if(fast==slow) return slow;

            fast=fast->next;

            slow=slow->next;

        }

        return NULL;

    }

};

int main()

{

    ListNode node1(),node2(),node3(),node4(),node5();

    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 ;

}