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).

The goal is to end up with the following 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:

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.