How to reverse a linked list in place

In-place reversal of a linked list reverses the linked list without using any additional data structure. This operation is handy in many situations. For instance, one practical use is displaying visited websites in reverse order. This helps quickly access recently browsed sites. It's also useful when we want to quickly delete the last few items from a long to-do list; the items are now at the front, saving us time scrolling. Sometimes, when we're working with a list of tasks, reversing it can help us tackle them in a more logical order, like starting with the last task and working our way backward.

In-place reversal of a linked list operates by modifying the pointers within the linked list. By rearranging the links, the last node becomes the new head of the reversed list, and the original head becomes the last node. Each node’s next pointer is updated to point to the previous node instead of the next node. In short, in an in-place reversal, the values stored in the nodes are not modified; only the links between the nodes are altered.

Algorithm

The algorithm of the in-place reversal of a linked list is given below:

Initialize three node pointers:
1. current: It initially points to the head of the linked list. This pointer represents the current node we're processing.
2. previous: It’s initialized with NULL. Afterward, it points to the node before the current node and is used to update the link of the current node.
3. follow: It keeps track of the node we need to move to in the next iteration, i.e., we update current with follow. Initially, it's set to NULL. We do this to keep track of the next node before we update the next pointer of the current node.
Start traversing the linked list until the current pointer becomes NULL. In each iteration:
1. Set the follow pointer to current.next. This step is crucial to keep track of the next node, as reversing the link will make the current node point to the previous node.
2. Update the next pointer of the current node to point to the previous node. This step reverses the link of the current node.
3. Move the previous pointer to the current node and the current pointer to the follow node. This prepares the pointers for the next iteration by moving them one step forward in the linked list.
Finally, we update the head of the linked list to the last node of the original linked list, which is now the head of the reversed linked list. This is done by pointing head to previous node.

Let’s look at the following illustration to get a better understanding of the solution:

main.py

linked_list_node.py

linked_list.py

print_list.py

from linked_list import LinkedList
from print_list import print_list_with_forward_arrow
def reverse(head):
    # Initialize previous and follow pointers as NULL
    previous, follow = None, None
    
    # Point current to the head node
    current = head
    
    # Iterate through the list until we reach the end
    while current is not None:
        # Store the next node in the follow pointer
        follow = current.next
        
        # Reverse the link of the current node to point to the previous node
        current.next = previous
        
        # Move previous to the current node
        previous = current
        
        # Move current to the follow node
        current = follow
    
    # Update the head to the last node, which is now the first node
    head = previous
    
    # Return the head of the reversed linked list
    return head
def main():
    input = (
        [1, 3, 5, 7, 9, 11],
        [2, 4, 6, 8, 10, 12],
        [3, 2, 1],
        [100],
        [1, 2],
    )
    for i in range(len(input)):
        input_linked_list = LinkedList()
        input_linked_list.create_linked_list(input[i])
        print(i+1, ".\tInput linked list: ", sep="", end="")
        print_list_with_forward_arrow(input_linked_list.head)
        print("\n\tReversed linked list: ", end="")
        print_list_with_forward_arrow(reverse(input_linked_list.head))
        print("\n", "-"*100)
if __name__ == "__main__":
    main()

Reverse linked list

Code explanation

Here is a line-by-line explanation of the reverse function implemented in main.py above:

Lines 6–9: We initialize the current, previous, and follow pointers.
Line 12: We use a while loop to iterate the entire linked list.
Line 17: We reverse the link of the current node by pointing its next pointer to the previous node.
Lines 20–23: We move the previous and current pointers one step forward.
Line 26: We update the head to point to the updated head of the reversed linked list.

Free Resources

How to reverse a linked list in place

Algorithm

Code implementation

Code explanation