Rotate a Linked List

Introduction

The linked list is one of the most important data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list and an integer X. We have to rotate the list counter-clockwise by X nodes.

Note: X is smaller than the count of nodes in the linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with help of example.

Suppose the given linked list 1 → 2 → 5 → 10 - 12 → 13, and the value of X is 4. Now, we have to rotate the given list counter-clockwise by X.

Here, rotating counter-clockwise a linked list by X means that the first X nodes of the linked list will be removed from the start and get appended to the end of the list.

In the given list, the first 4 nodes are 1 → 2 → 5 → 10. Now, these 4 elements will get appended to the end of the list. So, the final list will be:
12 → 13 → 1 → 2 → 5 → 10.

In this way, we are rotating the given first X nodes counter-clockwise.

Input :

Output :

Explanation : As the value of X is 4, so the first 4 nodes have been removed from the beginning of the linked list and appended at the end of the linked list.

Now, I think from the above example, it is clear what we have to do in this problem. So let’s move to approach.

Before directly jumping to approach in the next section, just try to think how will approach this problem?

It’s okay if your solution is not the best optimized solution, we will try to optimize it together.

This question is not a very complex one. We are going to make use of linked list traversal in this question. Let us have a glance at the approach.

Approach and Algorithm

The approach is going to be pretty simple.

Let us first think about what we need to perform the required task of rotating the list counter-clockwise by X nodes.

  • For linked list rotation, we have to change the next of Xth node to NULL, next of the last node to the head node, and finally, make the head point to the (X+1)th node.
  • So, we need Xth node, (X+1)th node and the last node.

To acheive the above objective of rotation:

  • We will traverse through the list and stop at the Xth node.
  • We will store the pointer to the Xth node.
  • The (X+1)th node can be reached using the next of Xth node. Now, we will keep traversing the list till the last node, and change the pointers as stated below:
    1) Change the next of Xth node to NULL
    2) Next of the last node to the head node.
    3) And finally, make the head point to the (X+1)th node.

Dry Run

Code Implementation





#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void rotate(Node** head_ref, int k)
{
    if (k == 0)
        return;

    Node* current = *head_ref;

    int count = 1;
    while (count < k && current != NULL) {
        current = current->next;
        count++;
    }

    if (current == NULL)
        return;

    Node* kthNode = current;

    while (current->next != NULL)
        current = current->next;
 
    current->next = *head_ref;

    *head_ref = kthNode->next;

    kthNode->next = NULL;
}

void push(Node** head_ref, int new_data)
{

    Node* new_node = new Node();

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}

int main(void)
{

    Node* head = NULL;

       push(&head, 13);
       push(&head,12);
       push(&head,10);
       push(&head,5);
       push(&head,2);
       push(&head,1);
     
 
    cout << "Given linked list \n";
    printList(head);
    rotate(&head, 4);
 
    cout << "\nRotated Linked list \n";
    printList(head);
 
    return (0);
}


public class LinkedList {
    Node head; 
    
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    void rotate(int k)
    {
        if (k == 0)
            return;

        Node current = head;

        int count = 1;
        while (count < k && current != null) {
            current = current.next;
            count++;
        }

        if (current == null)
            return;

        Node kthNode = current;

        while (current.next != null)
            current = current.next;


        current.next = head;

        head = kthNode.next;

        kthNode.next = null;
    }

    void push(int new_data)
    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;
    }

    void printList()
    {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();

        
            llist.push(13);
            llist.push(12);
            llist.push(10);
            llist.push(5);
            llist.push(2);
            llist.push(1);
            

        System.out.println("Given list");
        llist.printList();

        llist.rotate(4);

        System.out.println("Rotated Linked List");
        llist.printList();
    }
} 

Output

Given linked list
1 2 5 10 12 13
Rotated Linked list
12 13 1 2 5 10

Time Complexity: O(n), as list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to rotate a linked list. Linked List rotation is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Python Stack using a Doubly Linked List
Next post Check If A Linked List Is Circular Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *