R@M3$H.NBlog

[Linked List] Find Loop Node

17 September, 2013 - 3 min read

In this post we will discuss how to find the node that causes loop in linked list.

Following procedure explains on how to detect node that caused loop:

  • By following the procedure described in previous post (Slow pointer and fast pointer approach),  we found the loop detection node
  • Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list
  • Traverse both the pointers one at a time
  • Both the pointers meet at the node because of which there is a loop in the linked list

For example consider the following linked list where the loop is detected at node 5:

Dry run for the above example:

Take two pointers P1 and P2 pointing to node 1(head of the linked list) and node 5(loop detection point) respectively.

Iteration 1:

Iteration 2:

Iteration 3:

Here both of them meet at node that contains data as 3. Hence the node that causes loop in a linked list is node 3.

The following program finds out the node that causes loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package ds;
public class MergePointInLoopedList
{
    public MergePointInLoopedList()
    {
    }
    
    public ListNode returnLoopDetectionNode(ListNode loopedList)
    {
        ListNode fastNode = loopedList;
        ListNode slowNode = loopedList;
        
        while(fastNode.next.next != null)
        {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            
            if(slowNode == fastNode)
            {
                break;
            }
        }
        
        return slowNode;
    }
    
    public static void main(String[] args)
    {
        SingleLinkedList newList = new SingleLinkedList();
        newList.add(1);
        newList.add(2);
        ListNode loopNode = newList.add(3);
        newList.add(4);
        newList.add(5);
        ListNode endNode = newList.add(6);
        //  Creating a loop
        endNode.next = loopNode;
        
        ListNode loopedList = newList.getList();
        MergePointInLoopedList mergePointLoopedList = new MergePointInLoopedList();
        //  Assuming there is a loop in linked list and finding loop detection node
        //  Loop detection node is the one where slow pointer and fast pointer meet
        ListNode loopDetectionNode = mergePointLoopedList.returnLoopDetectionNode(loopedList);
        
        //  Now take pointers P1 and P2. Let P2 be at loop detection node and P1 be at the head
        // of the looped linked list
        
        ListNode P1 = loopedList;
        ListNode P2 = loopDetectionNode;
        
        while(P1 != P2)
        {
            P1 = P1.next;
            P2 = P2.next;
        }
        
        System.out.println("Merging point in linked list that has a loop is ... "+ P1.data);
   }
}

END