Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Change Start Node

Easy
0/40
Average time to solve is 20m
profile
Contributed by
8 upvotes
Asked in companies
AdobeAmazonGreendeck

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
7 11 13 17 19 23 29 -1
3
Sample Output 1:
19 7 11 13 17 23 29 -1
Explanation For Sample Input 1:
Removing the third node from the end of the linked list, i.e. 19 and make the head node of the linked list.
Sample Input 2:
13 1 19 3 9 -1
5
Sample Output 2:
13 1 19 3 9 -1
Hint

How can you find the ‘K’ th node from the end?

Approaches (2)
Brute Force

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

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).

Space Complexity

O(1)

 

We are not using any extra space. So overall, our space complexity will be O(1).

Code Solution
(100% EXP penalty)
Change Start Node
All tags
Sort by
Search icon

Interview problems

solved with 9/10 test cases passed.

Node *changeStartNode(Node *head, int k)

{

    //  Write your code here

    int n=1;

    if(head == NULL || head->next == NULL){

        return head;

    }

 

    Node *prev= NULL;

    Node *temp= head;

 

    while(temp->next!=NULL)

    {

        temp=temp->next;

        n++;

    }

    Node *temp1= head;

    

    for(int i=1;i<=n-k;i++)

    {

        prev=temp1;

        temp1=temp1->next;

 

    }

        prev->next=temp1->next;

        temp1->next=head;

        head=prev->next;

        return temp1;

}

beginners

58 views
0 replies
0 upvotes

Discussion thread on Interview Problem | Change Start Node

Hey everyone, creating this thread to discuss the interview problem - Change Start Node.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Change Start Node

 

254 views
2 replies
0 upvotes
Full screen
Console