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
#include

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 =
            (struct Node*) malloc(sizeof(struct 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) {
        printf("%d, ",node->data);
        node = node->next;
    }
    printf("%d ",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;
    printf( "Given linked list \n");
    printList(head);
    rotate(&head, N);
    printf( "\nRotated Linked list \n");
    printList(head);
    return 0;
}

#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;
}
class ReverseN 
{
static class Node
{
    int data;
    Node prev;
    Node next;
}
static Node head = null;
 
static void rotate( int N)
{
    if (N == 0)
        return;
    Node current = head;
    int count = 1;
    while (count < N && current != null)
    {
        current = current.next;
        count++;
    }
    if (current == null)
        return;
 
    Node NthNode = current;
 
    while (current.next != null)
        current = current.next;
 
    current.next = head;
    (head).prev = current;
    head = NthNode.next;
    (head).prev = null;
    NthNode.next = null;
}
static void push(int new_data)
{
    Node new_node = new Node();
    new_node.data = new_data;
    new_node.prev = null;
    new_node.next = (head);
    if ((head) != null)
        (head).prev = new_node;
        head = new_node;
}

static void printList(Node node)
{
    while (node != null && node.next != null)
    {
        System.out.print(node.data + " ");
        node = node.next;
    }
    if(node != null)
    System.out.print(node.data);
}
 
public static void main(String[] args)
{
    push(5);
    push(4);
    push(3);
    push(2);
    push(1);
 
    int N = 2;
 
    System.out.println("Given linked list ");
    printList(head);
    System.out.println();
    rotate(N);
    System.out.println("Rotated Linked list ");
    printList(head);
}
}
 

class Node:
	def __init__(self, next = None, prev = None, data = None):
		self.next = next
		self.prev = prev
		self.data = data

def push(head, new_data):

	new_node = Node(data = new_data)

	new_node.next = head
	new_node.prev = None

	if head is not None:
		head.prev = new_node

	head = new_node
	return head

def printList(head):

	node = head

	while(node is not None):
		print(node.data, end = " "),
		last = node
		node = node.next
	
def rotate(head, N):
	if N == 0 :
		return

	current = head

	count = 1
	while count < N and current != None :
		current = current.next
		count += 1

	if current == None :
		return

	NthNode = current

	while current.next != None :
		current = current.next

	current.next = head

	head.prev = current

	head = NthNode.next

	head.prev = None

	NthNode.next = None

	return head

if __name__ == "__main__":
	head = None

	head = push(head, 5)
	head = push(head, 4)
	head = push(head, 3)
	head = push(head, 2)
	head = push(head, 1)

	print("Given linked list")
	printList(head)
	print()
	
	N = 2
	head = rotate(head, N)

	print("Rotated Linked list")
	printList(head)

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.
[forminator_quiz id=”4247″]

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.

Leave a Reply

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