How to Reverse a Linked List in Python

A linked list is a linear data structure in computer science that provides constant-time addition and deletion of elements. It is made up of nodes.

A single node stores some data and the address of the next node. The next node stores its data and the address of the next node. A single node only knows about the node it is pointing to. It has no information about the nodes that are pointing to it.

This structure allows us to add new nodes and delete existing nodes in constant time, given the node before it, unlike arrays, where we have to copy an array to a new array or shift the elements of an array to create room for addition and deletion.

In arrays, one can access elements in constant time with the help of indexes. But with linked lists, it takes O(n) time to access an element, where n is the length of the linked list.

Since a linked list is similar to an array in terms of structure (linear), we can also perform operations such as sorting, filtering, and searching over linked lists. We can use sorting and searching algorithms such as bubble sort, insertion sort, merge sort, quick sort, selection sort, binary search, and linear search over linked lists.

This article will show how to reverse a linked list using Python. Note that the code snippet considers a Node class representing a block of a linked list.

The Node class shall look as follows.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Reverse a Linked List in Python

Refer to the following Python code to reverse a linked list in Python.

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

To understand the code, consider an example linked list, 1 -> 2 -> 3 -> 4 -> 5 -> None.

First, we declare three variables, previous, current, and next, that point to None, the head of the input linked list, and None, respectively. Next, we declare a while loop that ends when the current node points to None.

For each iteration:

• We store the next node of the current node in the next node.
• Set the next node of the current node to the previous node.
• Reset the previous node to the current node.
• Reset the current node to the next node.

The following table represents how the values of variables, namely, previous, current, and next, change when the algorithm is applied for the above example.

The table cells above display the value being stored by a node.