Problem statement:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Solution #1:

public ListNode findCycle2(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) {
            var slow2 = head;
            while (slow2 != slow) {
                slow = slow.next;
                slow2 = slow2.next;
            }
            return slow;
        }
    }
    return null;
}

Solution #2 with counter(useless but educative.com..):

public ListNode findCycle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    var fast = head;
    var slow = head;
    var cycleLen = 0;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) {
            cycleLen = calcCycleLen(slow);
            break;
        }
    }
    return findCycle(cycleLen, head);
}

private ListNode findCycle(int len, ListNode head) {
    if (len > 0) {
        var node = head;
        while (len >= 0) {
            node = node.next;
            len--;
        }
        while (head != node) {
            head = head.next;
            node = node.next;
        }
        return head;
    }
    return null;
}

private int calcCycleLen(ListNode head) {
    int len = 0;
    var node = head.next;
    while (node != head) {
        len++;
        node = node.next;
    }
    return len;
}

Time complexity:

O(N)

Space complexity:

O(1)

Approach:

Find cycle like in has cycle.