aboutsummaryrefslogtreecommitdiff
path: root/other/linked_list_cycle2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/linked_list_cycle2.cpp')
-rw-r--r--other/linked_list_cycle2.cpp31
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;
+ }
+};