Reversing a Linked List

Exploring and refreshing data structures and algorithms, you will inevitably find the question “how do you reverse a linked list?”. For this exercise, we assume a singly-linked list, with a head, and the last item pointing to null (as shown).

Linked List

Singly Linked List

The goal is to end up with the following linked list:

Reversed Linked List

Reversed Linked List

The question deliberately never states the time-complexity (O-complexity) or the space requirements. For our example, let’s strive for the fastest example, with minimal extra storage. Let’s call the original linked list “L1”.

The naive example would create a new linked list “L2”, iterate to the end of L1, copy the element, set the head of L2 to be the last element, and delete it from L1. In pseudo-code:

Create new empty linked list L2
while L1 is not empty
  for each element of L1
    if at the end of L1
      remove last element E of L1
      if L2 is empty
         head of L2 to E
      else
        iterate to end of L2
        add E to end of L2
      end if
    end if
  end for
end while


This is pretty much the worst implementation I could possibly think of. Not only do we have three nested loops, but we are also using double the storage! This makes the time complexity O(N^3). Early on, we are taught that even O(n^2) is terrible, so this is truly horrifyingly slow.

So, the second attempt should definitely try to clean up the time-complexity. The first inefficiency comes from the fact that we have to iterate over L2 to add a new element at the end of it. This is no good. Is there a way to insert in O(1) time? Why, yes! The fastest way is to create a new node with the next pointer pointing to the head, then set the head to the new node, like so:

Insert in O of 1

Inserting in O(1) Time

Pseudo-code:

function add(node N)
  N.next = head
  head = N;
end function

With this insert method we killed two birds with one stone: we got rid of the necessity to always iterate to the end of L1 — we can create L2 simply by iterating over L1, and adding each element to the beginning of L2 until we reach the end of L1:


create new empty linked list L2
for each node n in L1 (n = n.next)
  Make copy of n (call it M)
  set M.next = L2.head
  set L2.head = M
end for

The time complexity of this solution is O(n) and the space requirement is doubled because we end up with a copy of the linked list. To do this without the extra space, you would simply remove each element from L1 and add it to L2.


create new empty linked list L2
while L1 is not empty
  set n = L1.head
  copy n into m //without this, we couldn't access L1 anymore because the head is gone
  set n.next = L2.head
  set L2.head = n
  set L1.head = m.next
  remove m
end for

This is a pretty good solution: we are using the same amount of space in O(n) time. But we are still making a copy of the head so still using a little bit more space than necessary. The solution is to recursively iterate to the end of the linked list, set the head as the end, and return it.

Java code:

public Node reverse(Node n) {
  if (n.next == null) {
    return n;
  }
  Node newParent = reverse(n.next);
  if (newParent.next == null) {
    head = newParent;
  }
  
  newParent.next = n;
  return n;
}

Ta-dah! Reversing a Linked List in place in O(n) time with no extra memory requirements.

Leave a Reply