Last Updated: 1 Oct, 2020

Change Start Node

Easy

Asked in companies

Solve now

Problem statement

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

We could optimize the way of finding the 'K'th node in Approach-1. Instead of one pointer, we could use two-pointers.

Let's say we have two pointer names as "start" and "end". Initially, both are at the head of the linked list.
First, send the "end" pointer to the 'K'th node from the "head" of the linked list.
And then, start the "start" pointer from the beginning of the linked list. So, both pointers are exactly separated by 'K' nodes.
Now we will traverse in the linked list with maintaining the gap of the 'K' node until the "end" pointer does not reach the last node of the linked list.
When the "end" pointer reached the last node of the linked list, the position of the "start" pointer would be "K-1" th node.
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 the "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.

Solve now