Loops in Linked List

Problems with linked lists occur mainly while building or using a bad memory manager. Let us discuss two well known linked list problems.

Problem: Find if two linked lists short at some node. Find the node at which the two lists short.

Solution: show

Subtract the length of smaller list from the larger one. Move a pointer ahead on larger list by the difference of lengths. Now put a pointer on head of smaller list. More two pointers together. The point at which they meet is the point where they short. The following code gives the idea.

d = length(head1) - length(head2)
l1, l2 = head1, head2
if d < 0
  d *= -1 
  l1, l2 = head2, head1

ptr1 = l1
for i <- 1 to d
  ptr1 = ptr1->next

ptr2 = l2
while ptr1 != null
  if ptr2 == ptr1
    return ptr1

ptr1 = ptr1->next
ptr2 = ptr2->next

We can use this idea to find the shorted node to find the solution to next problem.

Problem: A linked list might contain a loop. How do we detect existence of the loop and find the node from which loop starts. Propose an O(n) time algorithm that doesn't take extra space and doesn't modify the linked list.

Solution: show

To find if the linked list contains a loop, run two pointers over the linked list, one that move one node at a time and other that moves two nodes at a time. Both of these pointers meet if the linked list contains a loop, otherwise the pointer moving with twice speed reaches the end while the slower pointer reaches midway.

fastptr = head
slowptr = head

while fastptr != null and fastptr->next != null
  fastptr = fastptr->next->next
  slowptr = slowptr->next
  if fastptr == slowptr
    return "loop exists"
return "loop doesnt exist"

If loop exists, then fast pointer meets the slow pointer before slow pointer completes one rotation of the loop. This fact can be easily proved. Once the pointers meet, we can count the number of nodes in the loop.

loopNodeCount = 0
do 
  loopNodeCount += 1
  slowptr = slowptr->next
while slowptr != fastptr
return loopNodeCount

Now using the trick used in the two linked list shorting problem above, we start two pointers, one from the head and other after advancing "loopNodeCount" nodes ahead. The node at which both the pointers meet is the loop node.

advptr = head
for i in range(1, loopNodeCount)
  advptr = advptr->next

normalptr = head
while normalptr != advptr
  normalptr = normalptr->next
  advptr = advptr->next
return advptr