Rotate a doubly linked list by N nodes

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}