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

Rotate Linked List

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
102 upvotes
Asked in companies
Morgan StanleyTata Consultancy Services (TCS)PharmEasy

Problem statement

You are given a linked list having ‘n’ nodes and an integer ‘k’.


You have to rotate the linked list to the right by ‘k’ positions .


Example :
Input: linked list = [1 2 3 4] , k = 2

Output: 3 4 1 2

Explanation:
We have to rotate the given linked list to the right 2 times. After rotating it to the right once it becomes 4->1->2->3. After rotating it to the right again, it becomes 3->4->1->2. 


Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line of the input contains a single integer 'n', denoting the number of nodes in the linked list.

The next line contains 'n' space-separated integers, denoting the elements of the linked list.

The next line contains an integer ‘k’, representing the number of positions up to the given linked list that has to rotate.


Output Format :
Return the head of the linked list after rotating it.


Note:
You do not need to print anything, it has already been taken care of. Just implement the given function. Elements of your returned linked list will be printed in a single line.


Sample Input 1 :
6
1 2 3 4 5 6
2


Sample Output 1 :
5 6 1 2 3 4


Explanation For Sample Input 1 :
For the first test case, after 1st clockwise rotation the modified linked list will be : 6->1->2->3->4->5
After, 2nd clockwise rotated the modified linked list will be : 5->6->1->2->3->4.
Thus the output is: 5 6 1 2 3 4.


Sample Input 2 :
3
3 6 9 
0


Sample Output 2:
3 6 9


Explanation For Sample Input 2 :
In this test case, ‘k’ is 0 therefore there will be no rotation, so the linked list remains unchanged.


Expected Time Complexity:
Try to do this in O(n).


Constraints :
1 <= n <= 10^5
0 <= Node.data <= 10^9 
0 <= k <= 10^5

Time Limit: 1 sec


Hint

Do the changes at (K+1)th node from last.

Approaches (2)
Brute Force

Find the length of the Linked List to check whether the ‘K’ is greater than the Length of the Linked List or not. Take a modulo of ‘K’ with its length if it is greater than the length. Reach the (‘K’+1)th node from last and change the pointers of nodes to get a rotated Linked List.
 

Here is the algorithm:
 

  1. Base Condition : If ‘HEAD’ is equal to ‘NULL’ or ‘K’ is equal to 0, then return ‘HEAD’ of the Linked List.
  2. Create a variable (say, ‘LEN’) which will store the length of the linked list and initialise it to 1.
  3. Create a temporary node (say, ‘TEMP’) which will be used to find the length of the Linked List and initialise it as ‘HEAD’.
  4. Run a loop while ‘TEMP’.next is not equal to ‘NULL’:
    • Update ‘TEMP’ as ‘TEMP’.next and increment the ‘LEN’ by 1.
  5. If ‘LEN’ is less than ‘K’, then update ‘K’ as ‘K’ % ‘LEN’ ( To make ‘K’ come in range of 0 to ‘LEN’).
  6. Update ‘K’ as ‘LEN’ - ‘K’ (To reach (‘K’+1)th node from end).
  7. If ‘K’ is equal to ‘LEN’, then:
    • Return ‘HEAD’ (Number of rotations are the same as length which will not change the original list).
  8. Create a variable (say, ‘COUNT’) which will be used to reach (‘K’ + 1)th node from end and initialise it to 1.
  9. Create a node (say, ‘CURRENT’) which will store the current node of Linked List and initialise it as ‘HEAD’.
  10. Run a loop while ‘COUNT’ is less than ‘K’ and ‘CURRENT’ is not equal to ‘NULL’:
    • Update ‘CURRENT’ as  ‘CURRENT’.next and Increment ‘COUNT’ by 1.
  11. If ‘CURRENT’ is equal to ‘NULL’., then return ‘HEAD’ of the Linked List.
  12. Update ‘TEMP’.next as ‘HEAD’  (Make the last pointer connect to ‘HRAD’).
  13. Update ‘HEAD’ as ‘CURRENT’.next (Make Kth node from last the new ‘HEAD’).
  14. Update ‘CURRENT’.next as ‘NULL’  (Make (‘LEN’ - ‘K’)th point to ‘NULL’).
  15. Finally, return the ‘HEAD’ of the Linked List.
Time Complexity

O(N), where ‘N’ is the size of the Linked List.

 

Since we are traversing all nodes of the Linked List to find the length and after that we are rotating the first ‘K’ nodes of the Linked List. Hence, the overall time complexity will be O(N).

Space Complexity

O(1)

 

Since we are not using any extra space, therefore space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Rotate Linked List
All tags
Sort by
Search icon

Interview problems

c++ best approach

Node*possible(Node*temp,int k){

     int cnt=1;

     while(temp!=NULL){

          if(cnt==k) return temp;

          temp=temp->next;

          cnt++;

     }

     return temp;

 

}

Node *rotate(Node *head, int k) {

     if(head==NULL || k==0){

          return head;

     }

     Node*tail=head;

     int len=1;

     while(tail->next!=NULL){

          len++;

          tail=tail->next;

 

     }

     if(k%len==0) return head;

     k=k%len;

     tail->next=head;

     Node*temp=possible(head,len-k);

     head=temp->next;

     temp->next=NULL;

     return head;

}

11 views
0 replies
0 upvotes

Interview problems

C++ solution iterative approach......

/**

 * Definition for singly-linked list.

 * class Node {

 * public:

 *     int data;

 *     Node *next;

 *     Node() : data(0), next(nullptr) {}

 *     Node(int x) : data(x), next(nullptr) {}

 *     Node(int x, Node *next) : data(x), next(next) {}

 * };

 */

int getLength(Node* head){

    int len = 0;

    while(head){

        len++;

        head = head->next;

    }

    return len;

}

Node *rotate(Node *head, int k) {

     if(!head)return 0;

     // Write your code here.

    int len = getLength(head);

    int acck = k%len;

    if(acck ==0)return head;

    int last = len - acck - 1;

    Node* lastnode = head;

    for(int i = 0;i<last;i++){

        lastnode = lastnode->next;

    }

    Node* newhead = lastnode->next;

    lastnode->next = nullptr;

    Node* temp = newhead;

    while(temp->next){

        temp = temp->next;

    }  

    temp->next = head;

    return newhead;

}

15 views
0 replies
0 upvotes

Interview problems

C++ soln.

 

Node *rotate(Node *head, int k) 

{

     if(head==NULL || head->next==NULL || k==0) return head;

        Node* curr=head;

        int cnt=1;

        while(curr->next)

        {

             curr=curr->next;

              cnt++;

        }

        curr->next=head;

         k=k%cnt;

         k=cnt-k;

     while(k--)

     {

          curr=curr->next;

     }

     head=curr->next;

     curr->next=NULL;

     return head;

}

33 views
0 replies
0 upvotes

Interview problems

Simple Solution - just play with links

/**

 * Definition for singly-linked list.

 * class Node {

 * public:

 *     int data;

 *     Node *next;

 *     Node() : data(0), next(nullptr) {}

 *     Node(int x) : data(x), next(nullptr) {}

 *     Node(int x, Node *next) : data(x), next(next) {}

 * };

 */

#include<bits/stdc++.h>

pair<Node*, int> sizeOfLL(Node* head) {

     Node* tail = head;

     pair<Node*, int> p;

     int cnt = 1;

     while(tail->next != NULL) {

          tail = tail->next;

          cnt++;

     }

     p.first = tail;

     p.second = cnt;

     return p;

}

 

Node* rotate(Node *head, int k) {

     pair<Node*, int> p = sizeOfLL(head);

     Node* tail = p.first;

     int size = p.second;

 

     int rotation = k%size;

     int x = size-rotation;

     if(x == 0)

          return head;

 

     int cnt = 1;

     Node* temp = head;

     while(cnt < x) {

          temp = temp->next;

          cnt++;

     }

     Node* tempHead = temp->next;

     if(tempHead == NULL) 

          return head;

 

     temp->next = NULL;

     tail->next = head;

     return tempHead;

}

15 views
0 replies
0 upvotes

Interview problems

Rotate Linked List

Node *rotate(Node *head, int k) {

     // Write your code here.

     if(head == NULL || head -> next == NULL || k == 0)

     return head;

 

     Node* temp = head;

     int len = 1;

     while(temp -> next != NULL){

          temp = temp -> next;

          len++;

     }

     temp -> next = head;

     k = k % len;

     for(int i=0; i<len-k; i++){

          temp = temp -> next;

     }

     head = temp -> next;

     temp -> next = NULL;

 

     return head;

}

50 views
0 replies
1 upvote

Interview problems

Python Solution: T.C-O(n)

def nthNode(head:Node , pos) -> Node:
    temp , cnt = head , 1

    while temp.next:
        if cnt==pos: return temp
        cnt+=1
        temp = temp.next
    return temp
    
def rotate(head: Node, k: int) -> Node:
    if head is None or k==0: return head

    tail , lens = head , 1
    while tail.next is not None: # finding the length of the linked list
        lens+=1
        tail = tail.next

    if k%lens==0: return head

    k = k % lens
    LastNode = nthNode(head,lens-k)
    tail.next = head
    head = LastNode.next
    LastNode.next = None
    
    return head
26 views
0 replies
0 upvotes

Interview problems

Java Solution

public class Solution {

    public static Node rotate(Node head, int k) {

        // Write your code here.

        if(head == null || head.next ==  null ){

            return head;

        }

        int cnt = 1;

        Node tail = head;

        while(tail.next != null){

            cnt++;

            tail = tail.next;

        }

        tail.next = head;

        Node temp = head;

        int count = cnt - (k % cnt);//count value is traversing form start;

        while(count > 1){

            temp = temp.next;

            count--;

        }

        head = temp.next;

        temp.next = null;

        return head;

    }

}

67 views
0 replies
0 upvotes

Interview problems

java || rotate LL by K

 public static Node rotate(Node head, int k) {

        Node tail=head;

        int len=1;

        while(tail.next!=null){

            tail=tail.next;

            len++;

        }

        //here we traverse and find the length of node;

        if(k%len==0) return head;

        //above condition says if no notation take place then simply return original LL

        tail.next=head;

        //after that we link tail node to head;

        k=k%len;

        Node temp=head;

        int cnt=1;

        while(temp!=null){

            if(cnt==(len-k)) break;

            cnt++;

            temp=temp.next;

        }

        head=temp.next;

        temp.next=null;

        return head;

    }

32 views
0 replies
0 upvotes

Interview problems

C++ Solution

Node *rotate(Node *head, int k) {
     int count=1;
     if(head==NULL || head->next==NULL) return head;
     Node*tail=head;
     while(tail->next!=NULL){
          count++;
          tail=tail->next;
     }

     int n=count-(k%count);

     Node*temp;

     while(n){
          temp=head;
          head=head->next;
          temp->next=NULL;
          tail->next=temp;
          tail=temp;
          n--;
     }
     return head;
}
201 views
0 replies
0 upvotes

Interview problems

Simple approach in C++

Node* rotateLinkedList(Node *head){     // this function rotate right by one node 
     Node* l=head, *lp=NULL;   
     while(l->next!=NULL){    // l is pointer to last and lp will point the last previous(After this loop)
          lp=l;
          l=l->next;
     }
     lp->next=NULL;
     l->next=head;
     head=l;
     return head;   // return the head of the linked list
}

Node *rotate(Node *head, int k) {
     Node *p=head;
     int cnt=0;
     if((head==NULL) || (head->next==NULL) || k==0){
          return head;
     }
     while(p!=NULL){   // count the number of nodes in the linked list
          cnt++;
          p=p->next;
     }
     p=head;
     k=k%cnt;  // If k is greater than the number of nodes in the linked list then make it lesser than the no. of nodes
     while(k>0){
          p=rotateLinkedList(p);
          k--;
     }
     return p;   
}
91 views
0 replies
0 upvotes
Full screen
Console