Last Updated: 22 Apr, 2022
Remove Loop
Easy
Asked in company
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 ].
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
Approaches
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’.