142. Linked List Cycle II

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;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容