700705. Rotate doubly Linked List
Easy
Rotate Doubly Linked List by P Nodes
Summary
Given a doubly linked list and an integer p, rotate the list to the right by p nodes. This problem involves manipulating a doubly linked list, where each node has references to both the previous (prev) and next (next) nodes.
Detailed Explanation
To solve this problem, we'll follow these steps:
- Initialize three pointers:
current,prev_node, andnew_tail. Setcurrentto the head of the list. - Move
currentpnodes to the right. Ifpis greater than the length of the list, movep % lengthnodes to the right (since rotating by the full length of the list is equivalent to not rotating at all). - Update
prev_nodeandnew_tailaccordingly:- Set
prev_nodeto the node beforecurrent. - Set
new_tailto the node aftercurrent.
- Set
- Update the
nextpointer ofprev_nodeto point tonew_tail. This effectively moves the tail of the list to the right bypnodes. - Update the
prevpointer ofnew_tailto point toprev_node. This sets the new head of the rotated list.
Here's a diagram illustrating the steps:
+----+ +----+ +----+
| A | | B | | C |
+----+ +----+ +----+
^ ^ ^
| | |
+----+ +----+ +----+
| prev_node | | current | | new_tail |
+----+ +----+ +----+
In the diagram, A is the original head of the list, and C is the original tail. The rotation moves the tail to the right by 2 nodes.
Time complexity: O(n), where n is the length of the list. Space complexity: O(1), as we only use a few extra pointers.
Optimized Solutions
Java
public class DoublyLinkedList {
public void rotate(int p) {
if (head == null || head.next == null) return;
Node current = head;
for (int i = 0; i < p && current.next != null; i++) {
current = current.next;
}
Node newTail = current;
while (newTail.next != null) {
newTail = newTail.next;
}
newTail.next = head;
head.prev = newTail;
}
}