Reversing a Linked List

Linked lists are an important data structure and also a popular source of interview questions. Few programmers will actually have to do a fully fledged linked list since most programming languages come with an implementation of it (usually of doubly linked lists). Nonetheless, understanding linked lists and other data structure will help you better understand runtime consequences of choosing one data structure over another.

Reversing a linked list is a common task. With a doubly linked list it is pretty obvious that you can reverse it in linear time and constant space by simply going through the list and swapping the next and previous reference.

Let us look at singly linked lists. The same performance is possible. A classic approach is to use recursion.

In Common Lisp:

(defun reverse-rec (l &optional (r nil))
  (if (null l)
    r
    (reverse-rec (cdr l) (cons (car l) r))))

In Java:

static class Node<T> {
    T v;
    Node<T> next;
    Node() { }
    Node(T v, Node<T> next) {
        this.v = v;
        this.next = next;
    }
}
static <T> Node<T> reverseRec(Node<T> l) {
    return reverseRec(l, null);
}
static <T> Node<T> reverseRec(Node<T> l, Node<T> r) {
    if (null == l) {
        return r;
    }
    return reverseRec(l.next, new Node(l.v, r));
}

So what is going on here? The variable l carries the part of list that needs to be reversed and r the part of the list that has already been resolved. In each recursion step we push the current value in front of the reversed list be creating a new node that points to the current r.

If your compiler supports optimizations for tail-recursion, this will not require any stack space. However, it can easily by transformed into an iterative algorithm that does not require a stack:

Common Lisp

(defun reverse-it (l)
  (do ((r nil (cons (car cur) r))
       (cur l (cdr cur)))
    ((null cur)
     r)))

Java:

static <T> Node<T> reverseIt(Node<T> l) {
    Node<T> r = null;
    while (null != l) {
        r = new Node(l.v, r);
        l = l.next;
    }
    return r;
}

So far we created new lists. The algorithms only need constant space outside the newly created lists, but what if we do not want to retain the original list. Doing an in-place replacement will be most efficient in this case. This is slightly more complicated. If you look at an element in the middle of the list, the next pointer needs to point to the previous element

Common Lisp:

(defun reverse-list (l)
  (loop
        :with prev = nil
        :if (null l) :return prev
        :do (rotatef (cdr l) prev l)))

Java

static<T> Node<T> reverseInPlace(Node<T> l) {
    Node<T> prev = null;
    while (null != l) {
        Node<T> nxt = l.next;
        l.next = prev;
        prev = l;
        l = nxt;
    }
    return prev;
}

So there you have it. Reversing a list is really straight forward. What is a bit more exciting, is to prove the correctness.