How to reverse a linked list

The linked list is a linear data structure, constructed by nodes. The linked list performed great in inserting and deleting elements. In a technical interview, linked list problems are frequently asked. In this post, I’ll introduce a classic problem in the linked list structure: reverse a linked list.

Intro

If you’re not familiar with the singly-linked list, here’s a brief introduction. A singly-linked list is constructed by nodes. Each node has a value and a pointer points to the next node. We can write a simple class:

class ListNode:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next

When building a linked list, we can first create some nodes, then linked them together. For example, if we wanna create a linked list: 1 -> 2 -> 3 , we can do:

first_node = ListNode(1, None)
second_node = ListNode(2, None)
third_node = ListNode(3, None)
first_node.next = second_node
second_node.next = third_node

Reverse a linked list

Assume we have a linked list: l = 1 -> 2 -> 3 -> 4 -> 5 -> None , we would like to reverse it to l = 5 -> 4 -> 3 -> 2 -> 1 -> None . There’re two ways to reverse such a list: iteratively and recursively. I’ll talk through both methods below.

Iteratively reverse a list

While we iterate over the list, we can change the current node’s next pointer to point to its previous node. Since we constantly change the connection between nodes, we need three variables to record the previous node, current node, and the next node. The following graph will illustrate this process:

Implementation:

def reverseList(head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        prev = None
        curr = head
        while curr.next:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        curr.next = prev
        return curr

Recursively reverse a list

In order to implement the recursive method, we first need to understand how this reverseList function works. reverseList will take one argument: the head of the original list, then return the head of the reversed list. Assume we have a list: n1 → … → nk-1 → nk → nk+1 → … → nm → None , if we apply this function to nk+1, then from node nk+1 to nm had been reversed and you are at node nk : n1 → … → nk-1 → nk → nk+1 ← … ← nm . The next step is to make nk+1’s next node points to nk. This can be easily achieved by: nk.next.next = nk .

Implementation:

def reverseList(head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        p = reverseList(head.next)
        head.next.next = head
        head.next = None
        return p

That’s how we reverse a linked list. Hope this post can help you understand how nodes are linked in a list.