Change Start Node

Posted: 1 Oct, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Input format :
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.
Constraints :
1 <= N  <= 5*10^5
1 <= K <= N
-10^9 <= data <= 10^9 and data != -1

Time Limit : 1 sec
Approach 1

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:

 

  • We will make a dummy node because, in some cases, when the list has only one element, we will have to operate those also. In that case, we don't have any previous node of 'K'th node, and we don't have any next of 'K'th node for which we can make the link between the previous node of 'K'th node and the next node of 'K'th node.
  • Our next node of "dummy" nodes will be the "head" of the list.
  • We will first find the length of the linked list say "len".
  • Now we need to find the "len-k-1" th node from the start of the list. Say new 'K' is "len-K-1".
  • First, store the 'K' th node because once we attach a link of "k-1" node to "k+1" node, we will lose the 'K'th node. So store the 'K'th node, let's say this node as "kThNode".
  • Attach the link of the "K-1"th node to "K+1" node.
  • Make "kThNode" as the head of the list in the following steps:
    • Make next of "kThNode" to the head of the linked list.
    • Now make the "head" of the linked list as "kThNode".
  • Return the modified "head" of the linked list.
Try Problem