Rotate Doubly Linked list by N nodes

The problem, simply

You get a doubly linked list (every box has a next arrow and a prev arrow) and a number N. Rotate it to the left by N: the first N boxes move, in the same order, to the end of the chain.

For example 10 20 30 40 50 60 with N = 2 becomes 30 40 50 60 10 20. Give back the new head, with prev and next correct everywhere. In this page n is the number of boxes and N is how far to rotate.

A story to remember it

Picture it

Examples

Way 1: the simple way

Rotate one step at a time, N times. One step means: take the head off, walk to the tail, and hook the old head after it.

1. Count the boxes and shrink N to N % n.
2. Repeat N times: unhook the head, fix the new head's prev to null, walk to the tail, hook the old head there with both arrows, and set its next to null.

class Solution {
    public Node rotate(Node head, int N) {
        if (head == null || head.next == null) return head;
        int n = 0;
        for (Node t = head; t != null; t = t.next) n++;
        N %= n;
        for (int step = 0; step < N; step++) {
            Node first = head;
            head = head.next;           // second box becomes the head
            head.prev = null;
            Node tail = head;
            while (tail.next != null) tail = tail.next;   // walk to the end
            tail.next = first;          // hook the old head at the back
            first.prev = tail;
            first.next = null;
        }
        return head;
    }
}

How long it takes: each of the N steps walks to the tail, about n boxes, so O(N * n). Extra room: O(1).

Way 2: the clever way

Tie the bracelet and snip once.

1. Walk to the tail and count the boxes n on the way.
2. Shrink N to N % n. If it is 0, give back the head.
3. Walk N - 1 steps from the head to find newTail, the box that will be last. The box after it is newHead.
4. Tie the ring: tail.next = head and head.prev = tail.
5. Snip: newTail.next = null and newHead.prev = null. Give back newHead.

class Solution {
    public Node rotate(Node head, int N) {
        if (head == null || head.next == null) return head;
        int n = 1;
        Node tail = head;
        while (tail.next != null) { tail = tail.next; n++; }   // find tail and length
        N %= n;
        if (N == 0) return head;

        Node newTail = head;
        for (int i = 1; i < N; i++) newTail = newTail.next;    // the Nth box
        Node newHead = newTail.next;

        tail.next = head;       // tie the ring
        head.prev = tail;
        newTail.next = null;    // snip
        newHead.prev = null;
        return newHead;
    }
}

How long it takes: one walk to the tail and at most one more partial walk, O(n). Extra room: O(1). Only four arrows change, no matter how big N is.

Watch out for

• Fix both arrows at the knot and at the snip. A doubly list with only next fixed reads fine forward but breaks when walked backward.
• Left or right? This problem moves the first N boxes to the back (a left rotation). Rotating right by k (LeetCode 61) is the same as rotating left by n - k % n.
• Empty chain and one box: return at once.

What interviewers ask next

• Rotate right by k instead. Find the box n - k % n from the start and cut after it, or cut after the (k % n)th box from the end using the two finger gap trick.
• Do it for a singly linked list. Same steps, minus the prev arrows.
• What if N can be huge, like a billion? N % n makes it the same work as a small N.
• Rotate each block of k boxes by d: cut the chain into blocks, rotate each block with this ring and snip trick, and stitch the blocks back together.

Remember this

Grown-up words: the bracelet is a circular linked list, the beads are nodes with prev and next pointers, and moving the first N boxes to the back is a left rotation.