Last Updated: 3 Dec, 2020
Loop Reconnect
Easy
Asked in companies
Given a linked list with a loop and all unique elements. If the loop starts at node X then break the loop from the last node and join it to a node just greater than X. If no such node exists then connect it to null.
For example:
Let the linked list be 1 -> 5 -> 2 -> 4 -> 3 -> 5 and then the last node is connected to node with value 4, which makes a loop. In this linked list, the loop starts from the node with value = 3 and ends at the node with value = 4.
You are supposed to break the loop ending at 4 and connect it to a node value just greater than 4, which is 5 in this case. So, the final answer is 1 -> 5 -> 2 -> 4 -> 3 and then the last node is connected to node with value 5.
Input format :
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
The second line of each test case contains a single integer X, this will be the position of the node to which tail will be connected (to form a loop). 'X' will not take 1 as its value.
Output format :
For each test case, return the head of the modified linked list.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= N
Time Limit :1 sec
Approaches
Using a slow pointer and a fast pointer, we can detect a loop in the linked list. The slow pointer gives the starting node of the linked list, and the fast pointer shows the ending node. Now we can traverse the whole linked list to find a node whose value is greater than the starting node. Then we take the ending node denoted by the fast pointer and connect it to the currently located node. If no such value exists, then we connect the ending node of the loop with null.
The steps are as follows:
- Initialize a ‘slow’ pointer to store the start of the loop, a ‘fast’ pointer to hold the end of the loop, and an ‘h’ pointer to keep the head of the LinkedList.
- Run an infinite while loop:
- Move ‘slow’ and ‘fast’ pointer to the next node.
- If ‘slow’ equals ‘fast’, then break from the loop.
- Initialize ‘startLoop’ to store the starting value of the cycle and store the ‘slow’ pointer’s value in it.
- Run an infinite while loop:
- While ‘fast’ is not equal to ‘slow’, keep moving ‘fast’ to the next node.
- Point the next pointer of the node to which ‘fast’ points to NULL.
- Initialize the ‘nextGreater’ pointer to store the value greater than the starting node value of the cycle.
- Run a while node till the ‘head’ is not equal to NULL:
- If the value of the head node is greater than the starting node’s value, then initialize ‘nextGreater’ with this value else, store NULL in it.
- Move the ‘head’ pointer to the next node.
- Connect the tail of the cycle to the ‘nextGreter’ node.
- Return ‘h’, which stores the head of the linked list.