Leetcode 142. Linked List Cycle II (Medium) (cpp)
Tag: Linked List, Two Pointers
Difficulty: Medium
/* 142. Linked List Cycle II (Medium) 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? */ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head == NULL || head -> next == NULL) { return NULL; } ListNode *s = head, *f = head; while (f != NULL && f -> next != NULL) { s = s -> next; f = f -> next -> next; if (s == f) break; } if (s != f) return NULL; while (head != s) { head = head -> next; s = s -> next; } return head; } };
