Loop Reconnect

Easy
0/40
Average time to solve is 45m
26 upvotes
Asked in companies
OYOGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
1 5 2 4 3 -1
4
1 2 3 4 5 6 -1
3
Sample Output 1 :
1 5 2 4 3 5
1 2 3 4 5 6 4
Explanation for Sample Output 1:
In the first test case,  there is a loop from ‘3’ to ‘4’. We break this loop and connect it to the node with a value just greater than ‘4’. So we connect the nodes with values ‘3’ and ‘5’. So the modified linked list becomes (1->5->2->4->3->5).

In the second test case,  there is a loop from ‘6’ to ‘3’. We break this loop and connect it to the node with a value just greater than ‘3’. So we connect the nodes with values ‘4’ and ‘6’. So the modified, linked list becomes (1->2->3->4->5->6->4).
Sample Input 2:
2
9 7 1 2 8 6 -1
2
3 2 1 -1
2
Sample Output 2:
9 7 1 2 8 6 8
3 2 1 3
Hint

Can you find the starting node of the loop and find the element just greater than it?

Approaches (1)
Floyd Cycle Detection

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.
Time Complexity

O(N), where ‘N’ is the number of elements in the Linked list.

 

As we are traversing every alternating element of the array, we have at most N/2 iterations. Hence, the overall complexity is O( N).

Space Complexity

O(1)

 

As we are not using any extra space, hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Loop Reconnect
Full screen
Console