diff options
Diffstat (limited to 'other/linked_list_cycle2.cpp')
-rw-r--r-- | other/linked_list_cycle2.cpp | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/other/linked_list_cycle2.cpp b/other/linked_list_cycle2.cpp new file mode 100644 index 0000000..43dccea --- /dev/null +++ b/other/linked_list_cycle2.cpp @@ -0,0 +1,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; + } +}; |