Reversing a Linked List

mgcadmin 28-10-2023

I see this question get raised on various forums and message boards all the time: "How do you reverse a Linked List?". I'm sure it's a leetcode question, but I'm too lazy to confirm. It's one of those questions that (nowadays) lacks real world applicability, yet remains in elementary programming courses to frustrate newbies, and more cunningly (and some what hilariously) in technical interview to trip up prospective employees.

Linked List's are recursively defined structures, and very often they are the first self referential data structure a programming student is introduced to. I mention that linked lists are defined recursively because I believe it is this very property that gets people so confused, just as with recursive functions.

Recursive data structures often have simple recursive algorithms to problems involving them, at least when compared to an iterative solution. Still, some people have trouble maintaining a "virtual stack" of the contents in their mind, and so find the iterative solutions to be more straight forward. There are some problems that can only be solved recursively, but often this is a consequence of arbitrary limitations.

Using Recursion

The algorithm to reverse list nodes in place isn't much longer than for just printing the values - though there are some subtleties that are easy to miss if you don't read the code carefully.

     //O(1) space(not including stack space), O(n) time
    public static Node revRec(Node h) {
        if (h.next == null) {
            return h;
        }
        Node newHead = revRec(h.next);
        h.next.next = h;
        h.next = null;
        return newHead;
    } 

Take a moment to really study this code. It might take a moment to convince yourself it actually works. Take note of when the pointer reassignment takes place, and which pointers are manipulated, as this is nitty gritty of the algorithm.

Iteratively Using An Explicit Stack

One of the conceptually simplest ways to reverse a linked list is to use an explicit stack instead of recursion. By Taking advantage of the stacks last-in first-out ordering, its as simple as placing each node on to a stack, and then popping them all off again, resetting the next values as you go.

    //O(n) space, O(n) time
    public static Node reverseWithStack(Node h) {
        Stack<Node> stack = new Stack<>();
        while (h != null) {
            stack.push(h);
            h = h.next;
        }
        Node dummy = new Node(0);
        Node t = dummy;
        while (!stack.isEmpty()) {
            t.next = stack.pop();
            t = t.next;
        }
        t.next = null;
        return dummy.next;
    } 

While straight forward, easy to implement, and easy to understand, this algorithm is also the lest efficient of the bunch. It requires two passes over the list, once to decompose the list, and again when reconstructing it. Thankfully, there is a single pass algorithm that does away with the stack entirely!

Iteratively With O(1) Space

In the previous algorithm we used an explicit stack to store the nodes, removing the Nodes from the stack in LIFO order, and constructing the list by appending the nodes to the end of the list (FIFO order). This algorithm can be thought of as the "dual" of the previous one. We remove nodes from the front of the list in FIFO order, and then reconstruct the list by pushing them into a new list in LIFO order, ultimately resulting in a reversed list.

     //O(1) space, O(n) time.
    public static Node reverseList(Node h) {
        Node dummy = new Node(-1);
        while (h != null) {
            Node x = h;
            h = h.next; //pop head off list, move head forward.
            x.next = dummy.next; 
            dummy.next = x; //push node to front of new list.
        }
        return dummy.next;
    } 

I'm sure there's still yet more ways that can be used to reverse the list, but seeing we have both an optimal iterative solution as well as a recursive solution, I think we can stop here. Until next time, Happy Hacking!

 

---