Problem of the day
You are given a singly linked list and an integer ‘K’. You are supposed to make ‘K’ th node from the end of a linked list as the starting node of the linked list.
Note :Given ‘K’ will always be valid.
The first line of the input 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 contains a single integer ‘K’.
Output format :
Print updated list elements separated by space.
Node :
You do not need to print anything; it has already been taken care of.
1 <= N <= 5*10^5
1 <= K <= N
-10^9 <= data <= 10^9 and data != -1
Time Limit : 1 sec
7 11 13 17 19 23 29 -1
3
19 7 11 13 17 23 29 -1
Removing the third node from the end of the linked list, i.e. 19 and make the head node of the linked list.
13 1 19 3 9 -1
5
13 1 19 3 9 -1
How can you find the ‘K’ th node from the end?
First, the fundamental idea is, find the length of the linked list and then subtract the "K-1" that would be the 'K'th node from the start of the linked list. The steps are as follows:
O(N), where ‘N’ is the number of nodes in the linked list.
We need to traverse the entire linked list to find the length of the linked list. And ‘K’ can have at most the size of the linked list. So overall time complexity will be O(N).
O(1)
We are not using any extra space. So overall, our space complexity will be O(1).