# Reverse a singly linked list

I came across this interesting programming question today and decided to give it a go. Given a singly linked list, with reference to the head node, reverse the linked list so the head node becomes the last node and vice versa.

This is my iterative solution:

``````public Node reverse(Node head) {
if (head == null || head.next == null) { // Linked list is empty or only has 1 node
return;
}
Node current = new Node();
Node next = new Node();
Node prev = null;

current = head; // current node starts at the first node, which is referenced by head. keep in mind that head acts like a pointer here instead of a real node
while(current != null) { //run loop as long as current node is not the last node
next = current.next; // stores a reference of the next node so we can manipulate current.next reference
current.next = prev; // point the current.next to the new reference position -which is in reverse order
prev = current; // prev has done its job of referencing the previous node, it now moves on to reference the subsequent node
current = next; // current has referenced in the new order, move current pointer to the next node - which is referenced by next pointer.
}
head = prev; // the last node is now the new first node in the linked list, so we reference head to prev, which points to the node itself
}
``````

Now let’s try the recursive solution:

### Identify base case

The base case occurs when we reach the last node of the linked list. We identify this case by verifying that current.next is NULL.

### Base case operation

In the base case, we need to set the head pointer to the very last node, which will in turn become the first node in the result.

``````public Node reverse(Node current) {
if (current == null) { //check for empty list
return;
}

if (current.next == null) { // at tail node, this is recursive base case
head = current; // set head to point to the last node in original list
return;
}

reverse(current.next);
current.next.next = current; // set the subsequent node as the current node
current.next = null; // set the previous node to null. which eventually means the older next pointer is used and null
}
``````

This little devil took me quite awhile to figure out as it’s very confusing between the reference pointers and the current nodes in question. But in practicality, i just can’t imagine a scenario where i’ll need to reverse a singly linked list. Can you? Whatever, this also proves that as a norm, we should just use a double linked list in the rare case we need to do a reversal like this. Time complexity of both of the solutions are O(n).

Edit: On a side note, we can also do a shallow copy of the linked list to an array-like data structure, use a reverse() function and push into a fresh linked list. Horrible on the space complexity, but alot easier to understand.