Remove Loop

Easy
0/40
profile
Contributed by
5 upvotes
Asked in company
Blackrock

Problem statement

Ninja is in the process of constructing a racecourse, which can be represented as a singly linked list. This list contains ‘N’ checkpoints, each represented as a node, and concludes at the final node.


However, Ninja accidentally connected the final checkpoint of the racecourse to the ‘Kth’ checkpoint (indexed from 0), creating an infinite loop for the racecars.


Your task here is to remove all the checkpoints that are in the loop and print the racecourse after the removal of the loop.


Refer example for better understanding.

Example : 
 N = 4
 K = 1
 NODE = 1->2->3->4


You can see there is a loop from the ‘1st’ node to the ‘3rd’ node (0 based), so we will remove all nodes from (1 - 3), so the answer is [ 1 ].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of the test case contains ‘N + 1’ space-separated where the first 'N' elements represent the LinkedList node, and the last integer is always '-1' representing the end of the LinkedList.

The second line contains a single integer ‘K’ denoting the start node of the loop.
Output format : 
Print the racecourse after removing loop nodes. It is guaranteed there will be at least one node after removal.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 1e5
0 <= K < N 

Sum of N <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
1 4 5 6 7 8 -1
3
4 5 7 6 -1
1
Sample Output 1 :
1 4 5 
4
Explanation Of Sample Input 1 :
For test case 1, 
Initially the racecourse looks like,


After removing, 6->7->8 (Nodes in the loop), our final LinkedList looks like this.


For test case 2,
Initially, the racecourse looks like,


After removing, 6->7->8 (Nodes in the loop), our final LinkedList looks like this.

Sample Input 2 :
2
1 4 5 6 -1
3
1 3 -1
1
Sample Output 2 :
1 4 5 
1
Hint

Can you create a new final node of the racecourse?

Approaches (1)
Greedy

APPROACH : 
 

  • We will break the problem down into a new rear node.
  • The ‘K - 1’th node as the new rear node, we will change ‘NEXT’ to ‘NULL’.
  • Taking care of ‘K == 0’, we don’t have ‘-1’th node in our list, we will return ‘NULL’.
  • Return new list.

ALGORITHM :

 

  • If ‘K == 0’, return ‘NULL’.
  • Subtract ‘1’ from ‘K’.
  • Create a pointer ‘TEMP’ equals to ‘HEAD’.
  • Start iterating over LinkedList, and subtract ‘1’, from ‘K’ and move ‘TEMP’ to ‘TEMP->NEXT’, if ‘K == 0’ break the loop.
  • Set ‘TEMP->NEXT’ as ‘NULL’
  • Return ‘HEAD’.
Time Complexity

O(N), where ‘N’ is the size of our linked list ‘HEAD’.

 

We will iterate over LinkedList only once. Hence, the overall Space Complexity is O(N).

Space Complexity

O(1), where O(1) represents constant space. 

 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

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