Difficulty: Medium

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

Advanced:

Can you use O(1) space to solve this problem?

Their thinking

Consider using fast or slow Pointers to solve this problem.

Use the fast and slow Pointers, one marked with slow and the other marked with fast, slow moves one bit at a time, and fast moves two bits at a time. If there are entry points, then slow and fast must meet within the ring.

If there is entry point P, then the distance from the starting point to the entry point is A, the distance from the entry point to the encounter point is B, and the distance from the encounter point to the other side of the entry point is C. And the speed of fast is twice that of slow. Based on the above equation, we can get:

A + N(B + C) + B = 2 * (A + B)
=> A = (B + C)(N - 1) + C
Copy the code

So we can see from this equation that if you go up the n-1 circle and then up the C distance, you can get to the entry point again, so consider introducing another pointer that starts at the beginning.

Answer key

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

        if (slow == fast) {
            ListNode node = head;
            while(node ! = slow) { node = node.next; slow = slow.next; }returnnode; }}return null;
}
Copy the code

test

LinkedListCycleII linkedListCycleII = new LinkedListCycleII();

private ListNode generateListNode(int[] node, int entryPoint) {
    if (node.length == 0) {
        return null;
    }
    ListNode listNode = new ListNode(node[0]);
    ListNode entryPointListNode = entryPoint >= 0 ? listNode : null;
    ListNode temp = listNode;
    for (int index = 1, length = node.length; index < length; ++index) {
        temp.next = new ListNode(node[index]);
        temp = temp.next;
        if (index == entryPoint) {
            entryPointListNode = temp;
        }
    }
    temp.next = entryPointListNode;
    return listNode;
}

@Test
public void test_slowFastPointer_case1(a) {
    ListNode head = generateListNode(new int[] {3.2.0, -4}, 1);
    Assertions.assertEquals(2, linkedListCycleII.detectCycleSlowFastPointer(head).val);
}

@Test
public void test_slowFastPointer_case2(a) {
    ListNode head = generateListNode(new int[] {1.2}, 0);
    Assertions.assertEquals(1, linkedListCycleII.detectCycleSlowFastPointer(head).val);
}

@Test
public void test_slowFastPointer_case3(a) {
    ListNode head = generateListNode(new int[] {1}, -1);
    Assertions.assertNull(linkedListCycleII.detectCycleSlowFastPointer(head));
}
Copy the code