Rotate Doubly linked list by N nodes

Introduction

The linked list is one of the most important concepts and 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 problem, we have been given a doubly linked list. Our task is to rotate the linked list counter-clockwise by N nodes. Here, N is a given positive integer which is smaller than the total number of nodes in the doubly linked list.

Problem Statement Understanding

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

For example, if the doubly linked list is:

and let's assume N to be equal to 2.

So according to the problem statement now we have to rotate the doubly linked list counter-clockwise by 2 nodes. To do, so the nodes with value A and B will be removed from their original positions and will be inserted at the end of the linked list, which will yield us our final resultant linked list as:

Given list:

Rotated list:

Similarly, if we are given a linked list as:

It means that we will have to rotate the above doubly linked list counter-clockwise by 4 nodes. To do, so we will move the first 4 nodes from the beginning to the end of the list such that our final linked list will be:

Some more Examples

Input:

Output:

Input:

Output:

Now I think from the above examples it is clear what the problem is demanding. So next we have to think how we can approach this problem towards a solution?

Let’s have a glance at approach.

Approach and Algorithm

The approach is going to be pretty simple.

So let’s first think about what we actually need to perform the task of rotating a doubly linked list by N nodes.

  • To rotate the doubly linked list by N nodes
    1) We need to change the next pointer of Nth node to NULL.
    2) Next pointer of last node (i.e. Last node of the doubly linked list) to head node.
    3) prev of head node to last node.
    4) And finally change head to (N+1)th node and prev of new head node to NULL (Since we know that in a doubly linked list, prev of head node is NULL).
  • So we basically need to get hold of these three nodes: Nth node, (N+1)th node and last node.

To achieve the above objective of rotation:

  • Start traversing the list from the beginning and stop at the Nth node.
  • Store the pointer to Nth node so that we can get (N+1)th node using NthNode->next.
  • We will keep traversing the list till the end of the list and store the pointer to the last node as well.
  • Finally, we will change the pointers as stated below.
    1) Change the next pointer of Nth node to NULL.
    2) Make next pointer of last node point to the head node
    3) Make prev of head node point to the to last node.
    4) Finally, make (N+1)th node the new head and point the prev of new head node to NULL.
  • Finally, following the above steps, our list will get rotated counter-clockwise by N nodes.

At last, print the rotated list using the PrintList function.

Dry Run


Code Implementation:

#include 
using namespace std;

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

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

    struct Node* current = *head_ref;
    int count = 1;
    while (count < N && current != NULL) {
        current = current->next;
        count++;
    }

    if (current == NULL)
        return;

    struct Node* NthNode = current;
    while (current->next != NULL)
        current = current->next;

    current->next = *head_ref;
    (*head_ref)->prev = current;
    *head_ref = NthNode->next;
    (*head_ref)->prev = NULL;
    NthNode->next = NULL;
}

void push(struct Node** head_ref, int new_c)
{
    struct Node* new_node = new Node;
    new_node->data = new_c;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
     *head_ref = new_node;
}

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

int main(void)
{
    struct Node* head = NULL;

    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    int N = 2;

    cout << "Given linked list \n";
    printList(head);
    rotate(&head, N);

    cout << "\nRotated Linked list \n";
    printList(head);

    return 0;
}

Output

Given linked list
1 2 3 4 5
Rotated Linked list
3 4 5 1 2

Time Complexity: O(L), where L is the length of the linked list, as only one traversal of the linked list is required.

So, in this article, you have learnt how to rotate a doubly linked list by N nodes. This is an important coding interview question. 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 Delete middle of linked list
Next post Move all occurrences of an element to end in a linked list

Leave a Reply

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