aboutsummaryrefslogtreecommitdiff
path: root/linked_list_cycle2.cpp
blob: 43dcceaa211a7305171239f1c3b032d761f082b4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 142. Linked List Cycle II
#include "leetcode.h"

/*
 * given 'head' of linked list, return node where the cycle begins. if there is
 * no cycle return null. there is a cycle in linked list of there is some node
 * in the list that can be reached again by continuously following the 'next'
 * pointer. internally, 'pos' is used to denote the index of the node that
 * tail's 'next' pointer is connected to. it is -1 if there is no cycle. note
 * 'pos' is not passed as parameter.
 */

class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast)
        break;
    }
    if (!(fast && fast->next))
      return NULL;
    while (head != slow) {
      head = head->next;
      slow = slow->next;
    }
    return head;
  }
};