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:
- Traverse the list to find the nth node from the beginning.
- Connect the tail node to the head and vice versa to create a circular structure.
- Update the head to the (n+1)th node from the beginning and update the new tail.
- 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
- Implement the
rotateByN
function. - If
head
is null orn
is less than or equal to 0, return. - Initialize
counter
to 0 andtemp
tohead
. - Traverse the list using a loop while
temp
is not null andcounter
is less thann
. Incrementcounter
and movetemp
to the next node. - If
counter
is equal ton
, settemp
totemp.prev
. - Connect the tail's
next
to the head and the head'sprev
to the tail to create a circular structure. - Update the
head
totemp.next
and update the new tail astemp
. - Set the
prev
of the new head to null and thenext
of the new tail to null to break the circular structure. - If
counter
is not equal ton
, 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.
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.
New Comment