Detecting a cycle in a linked list

Problem

Detect a cycle in a linked list and return the node that represents the start of the cycle.

Input

• head: a pointer to the linked list

Approach

First, lets concentrate on how to detect a cycle in a linked list.

There are numerous ways to brute force this, but the most efficient approach is to use two pointers - a slow pointer and a fast pointer.

The slow pointer moves forward one node at a time, and
the fast pointer moves forward two nodes at a time.

If a cycle was to exist, then our pointers will eventually see the same nodes over and over again. By having a pointer that moves one additional step forward at each iteration, we will eventually reach a point where the slow pointer points to the same node as the fast pointer.

Consider the following linked list sequence:

A -> B -> C -> A -> B -> C -> A -> B -> C ...

If we let slow start at A and fast start at A, they will traverse through the nodes in this fashion:

# of iterations	slow (pointer)	fast (pointer)
0	A (head)	A (head)
1	B	C
2	C	B
3	A	A

As you can see, after 3 iterations, both pointers will point to the same node.

Solution

def rotate_2d_array(A):  
    for j in range(0, len(A) // 2):
        for i in range(j, len(A) - 1 - j):
            old = A[j][i]
            A[i][~j], old = old, A[i][~j]
            A[~j][~i], old = old, A[~j][~i]
            A[~i][j], old = old, A[~i][j]

            A[j][i] = old

    return A

# Note that this function returns a boolean
def has_cycle(head):  
    slow = fast = head
    while slow and slow.next and fast and fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            return True
    return False

Returning the beginning of a cycle

When slow == fast, it might be believed that these two variables point to the node that represents the beginning of a cycle. However, this isn't the case.

Consider the following linked list sequence:

Z -> A -> B -> A -> B -> A -> B ...

If we let slow start at Z and fast start at Z, they will traverse through the nodes in this fashion:

# of iterations	slow (pointer)	fast (pointer)
0	Z (head)	Z (head)
1	A	B
2	B	B

Here, we have a match where slow and fast both points to node B.

Z -> A -> B -> A -> B -> A -> B ...

But looking at the actual sequence, we see that the cycle starts at node A.

Where is the beginning of a cycle?

The beginning of a cycle can be found by counting the length of the cycle. This can be done by taking a copy of the matched node above (slow or fast) and counting how many iterations it takes to get to the same matched node.

            temp = slow
            count = 0
            while temp:
                temp = temp.next
                count += 1
                if temp == slow:
                    break

Once we have the count of the cycle, we'll grab a fresh pointer to head called loop_start and move it forward by count times.

            loop_start = head
            for _ in range(count):
                loop_start = loop_start.next

Then we grab another fresh pointer to head called start, and iterate both of these pointers simultaneously (moving forward one node at a time) until we have a match.

            start = head
            while loop_start != start:
                loop_start = loop_start.next
                start = start.next

            return loop_start

The while loop above may look scary, but at this point we have already confirmed that a linked list cycle exists.

Putting everything together, we have:

def has_cycle(head):  
    slow = fast = head
    while slow and slow.next and fast and fast.next and fast.next.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast:
            temp = slow
            count = 0
            while temp:
                temp = temp.next
                count += 1
                if temp == slow:
                    break

            loop_start = head
            for _ in range(count):
                loop_start = loop_start.next

            start = head
            while loop_start != start:
                loop_start = loop_start.next
                start = start.next

            return loop_start

References: Floyd