Reverse a Doubly Linked list

The problem, simply

A doubly linked list is a chain where every box has two arrows: next points to the box after it, and prev points to the box before it. The first box has prev = null and the last box has next = null.

Turn the chain around. The last box becomes the first, and every next and prev must point the right way in the new order. Give back the new first box.

A story to remember it

Picture it

Examples

Way 1: the simple way

Leave the arrows alone and move the numbers instead, using a stack of plates.

1. Walk the chain and push every number onto a stack.
2. Walk the chain again from the head and pop a number into each box. The last number pushed comes off first.

import java.util.*;

class Solution {
    public Node reverseDLL(Node head) {
        Deque<Integer> plates = new ArrayDeque<>();
        for (Node cur = head; cur != null; cur = cur.next) plates.push(cur.data);
        for (Node cur = head; cur != null; cur = cur.next) cur.data = plates.pop();
        return head;   // same boxes, numbers in reverse
    }
}

How long it takes: two walks, O(n). Extra room: a stack as tall as the chain, O(n). Many interviewers reject this, because the boxes did not really move. If a box carried a big record instead of a number, copying would be costly.

Way 2: the clever way

Do the about face. Walk the chain with curr, and at each box swap next and prev.

1. Start with curr on the head.
2. Swap: tmp = curr.prev, curr.prev = curr.next, curr.next = tmp.
3. The box that used to come next is now in curr.prev, so move with curr = curr.prev.
4. Remember the last box you swapped. When curr becomes null, that box is the new head.

The picture shows the chain as two parts: the boxes that already turned around, read from their new head, and the boxes still waiting.

class Solution {
    public Node reverseDLL(Node head) {
        Node curr = head, last = null;
        while (curr != null) {
            Node tmp = curr.prev;      // about face: swap the two arrows
            curr.prev = curr.next;
            curr.next = tmp;
            last = curr;               // remember the box we just turned
            curr = curr.prev;          // the old next is now in prev
        }
        return last;                   // the old tail, now the head
    }
}

How long it takes: one walk, O(n). Extra room: two fingers, O(1). An empty chain returns null because last never changes.

Watch out for

• Returning head at the end. The old head is now the tail. Return the last box you turned.
• Fixing only the next arrows, as in a singly list. Then prev still points the old way and walking backwards gives the wrong order.
• Some versions keep a tail pointer too. If so, swap head and tail at the end.

What interviewers ask next

• Why is this easier than a singly list? Every box already knows its neighbor on both sides, so you never have to save the next box before changing an arrow. The swap keeps it.
• Reverse a doubly list in groups of k. Swap arrows inside each group, then hook each group's old first box to the next group's new first box, and fix that box's prev.
• Can you do it with recursion? Swap the arrows of the head, then reverse the rest starting from the new prev. Return the box whose new prev is null. It costs O(n) stack room.
• How do you check that your answer is right? Walk forward with next and backward with prev. Both walks must give opposite orders.

Remember this

Grown-up words: the two way chain is a doubly linked list, the boxes are nodes, the hands are the prev and next pointers, and the stack of plates is a stack.