Can we reverse a linked list in less than O(n)

The problem, simply

This is a thinking question. Normal reversal walks the whole list and flips every arrow, which takes O(n) time. Can we reverse a linked list faster than that?

The honest answer has two parts. For a plain singly linked list, no: there are n arrows that each have to change, and you cannot change an arrow without walking to it. For a doubly linked list that keeps both a head and a tail, yes in a sense: you do not need to move any arrow at all. Flip one switch that says "read from the other end", and the list behaves reversed in O(1).

A story to remember it

Picture it

Examples

Way 1: the simple way

The normal reversal with three fingers: prev, curr, next. Save next, flip the arrow, slide forward.

1. prev = null, curr = head.
2. While curr is not null: save next = curr.next, set curr.next = prev, then move prev and curr one step.
3. Return prev.

Why nothing can be faster on a one way list: the answer has n arrows, and every one of them is different from before. Changing an arrow means standing on its box, and the only way to reach a box is to walk there from the head. So at least n steps are needed, and this way uses exactly that many.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;   // hold on to the rest
            curr.next = prev;            // flip one arrow
            prev = curr;
            curr = next;
        }
        return prev;                     // every one of the n arrows changed
    }
}

How long it takes: one step per box, O(n), which is the best possible here. Extra room: three fingers, O(1).

Way 2: the clever way

Change the question. Most of the time nobody needs the arrows to physically point the other way. They need the list to act reversed: read from the other end, add to the other end. A doubly linked list that keeps head, tail and one flag can do that.

1. Keep head, tail and a flag flipped, which starts as false.
2. reverse() only does flipped = !flipped. That is O(1).
3. Every operation asks the flag which way to go. The front is flipped ? tail : head. The box after b is flipped ? b.prev : b.next. Adding at the end goes after the tail normally, or before the head when flipped.

class FlipList {
    static class Box {
        int val;
        Box prev, next;
        Box(int val) { this.val = val; }
    }

    private Box head, tail;
    private boolean flipped = false;          // true means read from tail to head

    public void reverse() { flipped = !flipped; }   // the whole reversal: O(1)

    private Box front() { return flipped ? tail : head; }
    private Box after(Box b) { return flipped ? b.prev : b.next; }

    public void addLast(int val) {
        Box b = new Box(val);
        if (head == null) { head = tail = b; return; }
        if (!flipped) { tail.next = b; b.prev = tail; tail = b; }   // real end is the tail
        else { b.next = head; head.prev = b; head = b; }            // real end is the head
    }

    public List<Integer> toList() {
        List<Integer> out = new ArrayList<>();
        for (Box b = front(); b != null; b = after(b)) out.add(b.val);
        return out;
    }
}

How long it takes: reverse() is O(1). Reading the list is still O(n), but it was O(n) anyway. Extra room: one flag, O(1).

Watch out for

• Code that walks the boxes directly with .next skips the flag and sees the old order. All access must go through the wrapper.
• The flag does not help a singly linked list. There is no prev arrow to follow, so there is nothing to switch to.
• Do not claim O(1) reversal without saying what you changed: a different structure (two way, with a tail and a flag), not a faster way to flip the same arrows.

What interviewers ask next

• What about an XOR linked list? Each box stores prev XOR next as one number. Walking needs the previous box, and it works the same in both directions. So swapping head and tail is a complete O(1) reversal, no flag needed.
• Can many processors do it faster? If you already have all n boxes in an array, n workers can each flip one arrow at the same moment, O(1) time with n workers. The total work is still n flips.
• Where is this idea used for real? Java 21 added reversed() on lists and deques. It returns a reversed view in O(1) that reads the same data from the other end, just like the flag. Deques in general let you treat either end as the front.
• Reverse a sublist from position m to n in one pass. That needs real arrow flipping: walk to m - 1, flip n - m + 1 arrows, and stitch both ends.
• Reverse a list using recursion. Same O(n) time, but the waiting calls use O(n) stack.

Remember this

Grown-up words: the bookshelf note is a direction flag (a reversed view), the one way strings are a singly linked list, the two way shelf is a doubly linked list with head and tail pointers, and "at least n steps" is a lower bound on the running time.