Calculate node that causes loop in a linked list

In previous post we discussed on how to detect a loop in linked list. 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.

Implementation for class ListNode and class SingleLinkedList can be obtained from previous post.

The following program finds out the node that causes loop:

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);
   }
}

In the next post we will discuss rest of the questions.