Rotate a doubly linked list by N nodes
Problem
Rotate the doubly linked list counter-clockwise by N nodes: the first N nodes move to the end, in order.
Example 1
Input: a ⇄ b ⇄ c ⇄ d ⇄ e, N = 2 Output: c ⇄ d ⇄ e ⇄ a ⇄ b
Also asked as: Rotate DoublyLinked list by N nodes · Rotate a Doubly Linked list in group of Given Size
Test cases
Case 1
Input: ["a","b","c","d","e"], 2 Expected: ["c","d","e","a","b"]
Case 2
Input: [1,2,3], 1 Expected: [2,3,1]
Case 3
Input: [1,2,3], 3 Expected: [1,2,3]
Case 4
Input: [1,2,3], 0 Expected: [1,2,3]
View solutionHide solution1 approach
1. Re-link at the Nth boundary
Time O(n)Space O(1)
Walk to node N; the node after it becomes the new head; splice the first N nodes onto the tail.
function rotateDLL(head, n) { if (!head || n === 0) return head; let cur = head; for (let i = 1; i < n && cur; i++) cur = cur.next; if (!cur || !cur.next) return head; const newHead = cur.next; let tail = newHead; while (tail.next) tail = tail.next; tail.next = head; head.prev = tail; newHead.prev = null; cur.next = null; return newHead;}