Rotate of Doubly linked list by n nodes

This article will discuss the implementation of rotating a doubly linked list by a given number of nodes in Java. Rotating a doubly linked list involves shifting nodes from the beginning of the list to the end while maintaining the doubly linked structure. We'll cover the problem statement, provide a step-by-step algorithm, Java code examples, and an explanation of the output.

Problem Statement

Given a doubly linked list and a positive integer n, the task is to rotate the list by n nodes in a circular fashion.

Example

Consider the following doubly linked list:

6 <-> 1 <-> 4 <-> 9 <-> 5 <-> 3 <-> 12

After rotating the list by 3 nodes, it should become:

9 <-> 5 <-> 3 <-> 12 <-> 6 <-> 1 <-> 4

Idea to Solve

To rotate the doubly linked list by n nodes, we need to follow these steps:

1. Traverse the list to find the nth node from the beginning.
2. Connect the tail node to the head and vice versa to create a circular structure.
3. Update the head to the (n+1)th node from the beginning and update the new tail.
4. Set the previous of the new head to null and the next of the new tail to null to break the circular structure.

Pseudocode

function rotateByN(n):
    if head is null or n <= 0:
        return
    initialize counter to 0
    initialize temp as head
    while temp is not null and counter < n:
        counter++
        temp = temp.next
    if counter is equal to n:
        set temp to temp.prev
        connect tail.next to head
        connect head.prev to tail
        set head to temp.next
        set head.prev to null
        set tail to temp
        set tail.next to null
    else:
        print "Given Nodes n are not exist"

Algorithm Explanation

1. Implement the rotateByN function.
2. If head is null or n is less than or equal to 0, return.
3. Initialize counter to 0 and temp to head.
4. Traverse the list using a loop while temp is not null and counter is less than n. Increment counter and move temp to the next node.
5. If counter is equal to n, set temp to temp.prev.
6. Connect the tail's next to the head and the head's prev to the tail to create a circular structure.
7. Update the head to temp.next and update the new tail as temp.
8. Set the prev of the new head to null and the next of the new tail to null to break the circular structure.
9. If counter is not equal to n, print "Given Nodes n are not exist".

If n is positive, the list is rotated to the right or clockwise, which means the last n nodes are moved to the front of the list, and the first (size - n) nodes are moved to the end of the list.

Program Solution

1) Rotate doubly linked list by n nodes in java 2) Rotate doubly linked list by n nodes in c++ 3) Rotate doubly linked list by n nodes in c# 4) Rotate doubly linked list by n nodes in php 5) Rotate doubly linked list by n nodes in python 6) Rotate doubly linked list by n nodes in ruby 7) Rotate doubly linked list by n nodes in swift 8) Rotate doubly linked list by n nodes in kotlin 9) Rotate doubly linked list by n nodes in c 10) Rotate doubly linked list by n nodes in scala 11) Rotate doubly linked list by n nodes in node js 12) Rotate doubly linked list by n nodes in vb.net 13) Rotate doubly linked list by n nodes in golang 14) Rotate doubly linked list by n nodes in typescript

Time Complexity

The time complexity of rotating a doubly linked list by n nodes is O(n), where n is the number of nodes in the list. We traverse the list to find the nth node and perform constant-time operations to rearrange the pointers.