Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1
Example 2:
Input: head = [1,2], pos = 0 Output: tail connects to node index 0
Example 3:
Input: head = [1], pos = -1 Output: no cycle
Follow Up:
Can you solve it without using additional space?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast = slow = p = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if fast is None or fast.next is None:
return None
while slow != p:
p = p.next
slow = slow.next
return p/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) return null;
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}