Rotate Doubly linked list by N nodes

Last Updated on November 22, 2022 by Prepbytes

Most of the linked list questions are not that complicated as they seem because a normal logic can be applied. Lets just say we have to rotate doubly linked list by n nodes. To approach this code, we will simply make the last node pointed to the head of the first node and make it circular. And then we will remove the next pointer after n nodes and to make it un-circular. So, in this article, let’s get into the approach to rotate doubly linked list by n nodes.

How to Rotate Doubly Linked List by N Nodes

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.

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 to rotate doubly linked list by n nodes

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.

1. To rotate the doubly linked list by N nodes
   • We need to change the next pointer of N^th node to NULL.
   • Next pointer of last node (i.e. Last node of the doubly linked list) to head node.
   • prev of head node to last node.
   • 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).
2. So we basically need to get hold of these three nodes: N^th node, (N+1)^th node and last node.

To achieve the above objective of rotation:

1. Start traversing the list from the beginning and stop at the N^th node.
2. Store the pointer to N^th node so that we can get (N+1)^th node using NthNode->next.
3. We will keep traversing the list till the end of the list and store the pointer to the last node as well.
4. Finally, we will change the pointers as stated below.
   • Change the next pointer of Nth node to NULL.
   • Make next pointer of last node point to the head node
   • Make prev of head node point to the to last node.
   • Finally, make (N+1)^th node the new head and point the prev of new head node to NULL.
5. 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 to rotate doubly linked list by n nodes

Code Implementation to rotate doubly linked list by n nodes

#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 to rotate doubly linked list by n nodes: O(L), where L is the length of the linked list, as only one traversal of the linked list is required.

Conclusion

So, in this article, We have implemented a simple logic irrespective of how complex the question was. We basically made a linked list into a circular one then removed the link after n nodes to make it un-circular. So that is how we rotate doubly linked list by n nodes. Enthusiastic about more questions visit the link and find all questions of linked lists.Linked List.

FAQs

1. Why a doubly linked list is preferred than a singly linked list?
Doubly linked list is a bi- directional list, which means it can be traversed through both sides. So, finding elements in a doubly linked list is far more easy.

2. What is the time complexity of reversing a doubly linked list?
The time complexity of reversing a doubly linked list is O(n).

3. What is the most efficient way to reverse a doubly linked list?
The iterative approach where we assign pointers, head, and current node as null and traverse through the lists.