141/142 Linked List Cycle I/II

141 Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space?

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

Similar to CTCI 2.6 Given a circular linked list, return the node at the beginning of the loop

resource: http://coderevisited.com/how-to-detect-if-a-linked-list-has-a-loop/

Part 1(141):Detect if Linked List Has a Loop

Runner Approach - FastRunner moves two steps at a time, while SlowRunner moves one step. If linked list contains loop or cycle than both fast and slow pointer will meet at some point during iteration. If they don't meet and fast or slow will point to null, then linked list is not cyclic and it doesn't contain any loop.

And they must eventually meet.

Part 2: When do they collide? (slow == fast)

Assumed:

the "non-looped" part is size of k; Known:
every p steps slowRunner takes, fastRunner takes 2p

Therefore:

After slowRunner took k steps to enter the loop, fastRunner has taken 2k steps total, and must be 2k-k=k steps in the loop -> Write it as mod(k, LOOP_SIZE) steps
The relative position between slowRunner and fastRunner will have following facts:
- slowRunner is 0 steps into the loop;
- fastRunner is k steps into the loop;
- slowRunner is k steps slower than fastRunner;
- fastRunner is LOOP_SIZE - k steps behind slowRunner;
- fastRunner catches up to slowRunner at a rate of 1 step per unit of time

So, when do they meet? they meet after (LOOP_SIZE - k) steps

Part3: How to find the start of the loop?

Because K = mod(k, LOOP_SIZE), or in other words, k = (M * LOOP_SIZE) + K, for any integer M; It's k nodes from the loop start.

Optimization:

- Brent’s Cycle detection Algorithm

This algorithm is based on Floyd‘s algorithm. It is more efficient (24-36% faster on average) than Floyd‘s but little complicated.

Start ptr1 (Moving ptr), ptr2 (Stationary pointer) from beginning of the list ptr1 takes one step per iteration, If it is then at the same position as the ptr2, there is obviously a loop. If it reaches the end of the list, there is no loop. Teleport ptr2 position to ptr1 position occasionally. We start out waiting just 2 steps before teleportation, and we double that each time we move the ptr2.

Extension:

- The length of the loop:

Use Floyd’s cycle detection algorithm to find if there is a loop.

After finding the loop, Initialise slowptr to fastPtr.
Keep moving slowptr and until it come back to fastptr, use a counter variable when moving slowptr.

private static int findLengthOfTheLoop(SinglyLinkedListNode head) {
    SinglyLinkedListNode fastPtr = head;
    SinglyLinkedListNode slowPtr = head;
    boolean loopExists = false;
    while (fastPtr != null && fastPtr.getNext() != null) {
        fastPtr = fastPtr.getNext().getNext();
        slowPtr = slowPtr.getNext();
        if (slowPtr == fastPtr) {
            loopExists = true;
            break;
        }
    }
    int length = 0;
    if (loopExists) {
        do {
            slowPtr = slowPtr.getNext();
            length++;
        } while (slowPtr != fastPtr);
    }

    return length;
}

Code:

141

public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;

        while(fa != null && fast.next != null)

            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow)
            {
                return true;
            }
        }
        return false;

    }

142

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        /*
        * Find if there's a loop, if so get the meeting point after the loop
        */
        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
            {
                break;
            }
        }

        /*
        * If there's no meeting point, there won't be a loop
        */
        if(fast == null || fast.next == null)
        {
            return null;
        }

        /*
        * Keep the meeting point in the fast, and move the slow point to the head.
        * Slow and fast are both moving in the same pace, and are k steps from the loop starts 
        */
        slow = head;
        while(slow != fast)
        {
            slow = slow.next;
            fast = fast.next;
        }

        /*
        * now slow = fast, are both at the start of the loop
        */
        return slow;
    }

141/142 Linked List Cycle