Mafia and Cyclic List

Moderate
0/80
profile
Contributed by
3 upvotes
Asked in company
OYO

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 7 2
1 2 3 4


4 16 2    
1 2 3 4

Sample Output 1 :
4
3
Explanation Of Sample Input 1 :
For test  case 1:
After the first step Mafia will be at 2.
After the second step Mafia will be at 3.
After the third step Mafia will be at 4.
After the fourth step Mafia will be at 3.
After the fifth step Mafia will be at 4.
After the sixth step Mafia will be at 3.
After the seventh step Mafia will be at 4.


For test case 2:
Mafia will move from 1, like this :
2, 3, 4, 3, 4, 3, …
So, we can say that after the cycle starts, every second element is the same.
So if the 2nd, 4th, 6th… element is 3, so the 16th element is also 3.
Sample Input 2 :
2
5 2 2
1 2 3 4 5


5 10 2
1 2 3 4 5

Sample Output 2 :
3
5
Hint

Simulate the problem statement.

Approaches (2)
Brute Force

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

O(K), where 'K' is the number of steps.

 

We are moving until 'K' is greater than 0, so the time complexity is O(K).

Space Complexity

O(1).

 

As we are taking only constant extra space, so the space complexity is O(1).

Code Solution
(100% EXP penalty)
Mafia and Cyclic List
Full screen
Console