美文网首页
142. Linked List Cycle II

142. Linked List Cycle II

作者: juexin | 来源:发表于2017-01-09 19:09 被阅读0次

    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;
        }
    };
    

    相关文章

      网友评论

          本文标题:142. Linked List Cycle II

          本文链接:https://www.haomeiwen.com/subject/hephbttx.html