Last Updated: 30 Mar, 2022
Mafia and Cyclic List
Moderate
Asked in company
Mafia has a cyclic list, his friend challenged him to solve the following problem with the linked list.
Given a linked list, it is sure that the linked list contains a cycle. You start from the head and keep on going to the next node. You do this exactly 'K' times, return the last node where you will reach after moving 'K' steps.
Help Mafia to find the solution to this problem.
For Example :
Linked list :
Suppose K = 6
Initially, you will be at Node 1.
After first step -> Node 2
After second step -> Node 3
After third step -> Node 4
After fourth step -> Node 5
After fifth step -> Node 2
After sixth step -> Node 3
At the end, you will be at Node 3, so Node 3 is the answer.
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains three space-separated integers, 'N', 'K', 'S', denoting the length of the given linked list, the number of steps, and starting index of the linked list cycle respectively.
The second line contains 'N' space-separated positive integers, which are the values present in nodes of the linked list.
Note: You will not get 'S' in the function, it is only to show how the linked list cycle is present.
Output format :
For each test case, return the node where you will reach after moving exactly 'K' steps.
Constraints :
1 <= T <= 10
2 <= N <= 10^5
1 <= K <= 10^9
0 <= S < N - 1
1 <= A[i] <= 10^9
It is guaranteed that the sum of 'N' <= 10 ^ 5 in all the test cases.
Time Limit: 1 sec
Approaches
Approach :
Start from the given head, and move exactly 'K' steps.
Algorithm:
- Create a pointer as 'itr' to iterate over the linked list.
- Initialize 'itr' with head of the given LinkedList.
- Iterate until 'K' is greater than 0:
- Decrement 'K' by 1.
- Change 'itr' to 'itr->next'.
- Return 'itr'.
Approach :
Find the starting element of the cycle and length of the cycle, now suppose if you are at the starting element of the cycle and the length of the cycle is 'l' and you have to move 'X' steps, so moving 'X' steps is the same as moving 'X' % 'l' steps, because every time you move 'l' steps you will come back to the same position, so we will eliminate as many multiples of 'l' as we can, and in the end, the remaining steps will be 'X' % 'l'. Where '%' stands for modulus.
Suppose we have take 'Y' number of steps to reach the starting point of the linked list cycle then the value of 'X' is min(0, 'K - X'). Hence after iterating till the starting point of the linked list cycle, we just need to iterate 'X % I' steps more.
Algorithm:
- Create two pointers, 'fast' and 'slow' both pointing to the head of the given linked list.
- Move slow 1 step and fast 2 steps i.e. 'slow = slow->next' and 'fast = fast->next->next'.
- Declare an integer variable 'nodesInLoop' to count the number of nodes in the cycle.
- Move fast and slow pointer as follows:
- 'While(fast != NULL and fast->next != NULL)'
- 'if(slow == fast)', call the helper function 'loopNodes' to calculate the number of nodes in the linked list cycle and store in 'nodesInLoop', and break out of the while loop.
- 'slow = slow->next'.
- 'fast = fast ->next'.
- 'While(fast != NULL and fast->next != NULL)'
- Declare a node 'startOfCycle' set to 'slow' to store the starting node of the linked list cycle.
- Declare an integer variable 'steps = K' and a Node 'iterator'.
- 'While(steps--)'
- 'Iterator = iterator->next.'
- 'If(iterator == startOfCycle)', break out of the while loop.
- If steps remaining is greater than 0:
- it implies we need to move in the loop and as explained, moving 'steps' time in a loop is equivalent to moving 'steps % nodesInLoop' time.
- Update 'steps = steps % nodesInLoop'.
- 'While(step--)'
- 'iterator = iterator->next'.
- In the helper function 'loopNodes' with parameter as Node pointer 'current'.
- Initialize an integer variable 'res = 1'.
- Declare a Node pointer 'temp' as 'current'.
- 'While(temp->next != current)'
- Increment res by 1 i.e. 'res++'.
- Move temp by 1 step i.e. 'temp = temp->next'.
- Return 'res' as the final count of nodes in the cycle.
- Return 'iterator' as the final output.