Posted on by Kalkicode

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
while temp is not null and counter < n:
counter++
temp = temp.next
if counter is equal to n:
set temp to temp.prev
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.

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.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post