142. Linked List Cycle II

2017-01-09  本文已影响0人  juexin

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:Can you solve it without using extra space?

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        if(head==NULL)
          return NULL;
        while(p1&&p2&&p2->next)
        {
            p1 = p1->next;
            p2 = p2->next->next;
            if(p1==p2)
              break;
        }
        if(p2==NULL||p2->next==NULL)
          return NULL;
        p1 = head;
        while(p1!=p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};
上一篇 下一篇

猜你喜欢

热点阅读