How to reverse a singly linked list

Reverse a linked list iterative algorithm

1. The head node’s next pointer should be set to NULL since the head will become the tail. This is an exception for the head node, and can be done outside the while loop. But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.

2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.

3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.

4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.

Reverse a linked list iterative solution in Java

public reverseListIteratively (Node head)
{
if (head == NULL || head.next == NULL)
return;  //empty or just one node in list

Node Second = head.next;

//store third node before we change 
Node Third = Second.next;  

//Second's next pointer
Second.next = head;  //second now points to head
head.next = NULL;  //change head pointer to NULL

//only two nodes, which we already reversed
if (Third == NULL)
return;  

Node CurrentNode = Third;

Node PreviousNode = Second;

while (CurrentNode != NULL)
{ 
Node NextNode = CurrentNode.next;

CurrentNode.next = PreviousNode;

/*  repeat the process, but have to reset
     the PreviousNode and CurrentNode
*/

PreviousNode = CurrentNode;
CurrentNode = NextNode;  
}

head  = PreviousNode; //reset the head node
}

Reverse a linked list recursive Java

Now, let’s find a recursive solution in Java for this problem. The advantage that we have with recursion is the fact that we can go to the very end of the linked list and work backwards to reverse the list starting from the every end. This is because with recursion we can go to the very end of the linked list, but also essentially “save” our place in each and every node we traverse so that we can go backwards and change the pointers in the linked list so that the list is reversed – if you are rusty on recursion you can read our Recursion tutorial.

Base case for recursive solution

Before we come up with our recursive case, we should come up with our base case for this problem. The base case is what we use to essentially stop the recursion from continuously running. So, when should we stop the recursion from running – try to see if you can come up with this scenario on your own.

The base case for this problem will actually occur whenever we reach the tail node of the linked list – and by “tail” node we mean the very last node. We will know that we have reached the tail node when the current node’s next node is NULL – so the current node will be the tail node.

What should be done in the base case for this recursive problem?

Now, we know what the base case is and how to check for it, but what exactly should we be doing in this case? Well, we obviously want to have a return statement so that we can put a stop to the recursion. But, is there anything else that we should be doing here as well? It turns out that there is something else we need to do in the base case, because in the base case we are at the very end of the linked list. This means that because we are trying to reverse the list, we need to set the head pointer to point to the very last node.

This means that our base case would look like this – remember that we are assuming that in the recursive case, we will just be passing in the very next node in the linked list to the recursive function:

Java code for recursive solution’s base case:

/* if we are at the TAIL node: 
*/
if(currentNode.next == NULL) 
{ 
//set HEAD to TAIL since we are reversing list
head = currentNode; 
return; //since this is the base case
}