Leetcode 206: Reverse (Singly) Linked List

Iterative and recursive solutions explained with analogies

Link to problem descriptions

Basic data structure setup for singly linked list

Singly linked list is a linear data structure where elements, called nodes, are linked using pointers. It is called “singly” because each node only has a single pointer pointing to the next node, and thus there is only one path to traverse from the beginning (the head) to the end of the list.

Each node consists of two components:

1. Value/data: The data that the node stores
2. Next (the pointer): A pointer points to the address of the next node in the list

Python implementation of such a node is as follows:

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

Analogy setup

We can picture ourselves having a stack of books that need to be restacked in reverse order for both iterative and recursive solutions.

Iterative solution

For the iterative solution, we put the original stack to our left, and we want to form another stack to our right by moving the books one at a time from left to right.

The key is to track and update the following references/pointers:

• current : The topmost book on the left stack that we are moving from
• next_node : The book immediately next/underneath to the book we are moving
• previous : The topmost book that is on the right stack

At each step of the book moving, the implementation is best pictured in two stages:

• Stage 1: Doing the current work of moving current to the right stack
• Stage 2: Prepare for the next step — Once current is moved to the right stack, update its identity to previous ; change current into next_node so we move on to the next step

# When moving each book

# Stage 1:
#   keeping a note on `next_node`
next_node = current.next
#   then moving `current` to the right stack where `previous` is on the top
current.next = previous

# Stage 2: Once the move is done. update state
#   1. original `current` now become the topmost book on the right pile
previous = current
#   2. Move on to `next_node`
current = next_node

Putting these together, we get the following iterative solution:

class IterativeSolution:
    def reverseList(self, head: ListNode) -> ListNode:
        # At the very beginning, the right stack is empty,
        #   we start from the head of the left stack
        previous = None
        current = head

        # Loop as long as the left stack is not empty
        while current:
            # Moving each node(book)
            # Stage 1:
            #   keeping a note on `next_node`
            next_node = current.next
            #   then moving `current` to the right pile where `previous` is on the top
            current.next = previous

            # Stage 2: Once the move is done. update state
            #   1. original `current` now become the topmost book on the right pile
            previous = current
            #   2. Move on to `next_node`
            current = next_node

        # At the end, return the head of the right stack
        return previous

• O(1) space complexity: We only used three variables current , previous , and next_node
• O(n) time complexity: We loop through the linked list once

Recursive solution

The recursive solution that I favour could be pictured in the following scenario: Imagine we now have a team of people working on the same task, but each team member would only take the topmost book and then pass the rest of the pile to the next member with a request — “Please reverse the rest of the book. Once you are done, please return the reversed stack to me so I can put the one I kept at the bottom to finish the reversal”. This same operation repeats as each team member holds onto one book and passes the rest (a reduced stack) to the next person in line. This passing is equivalent to adding a function call to the call stack each time.

Once the stack reduces to have just one single book (i.e., as we reach the end of recursion descent), the team member who is handed this book can finally start to return the abovementioned “reversed stack” to the one before them (recursion ascent). This person takes the pile, puts the book they hold onto during recursion descent to the bottom of the pile, and the process repeats until we complete the recursion ascent (when the last call in the call stack is returned).

The trick here is to implement the four steps:

1. Pick the topmost book and hold onto it
2. Pass the rest of the stack to the next team member (i.e., the next recursive call)
3. Wait till the reversed stack is returned
4. Put the holdout book at step 1 to the bottom of the reversed stack

Here step 4 is easy to implement, but we must keep in mind that we need to wait till the reversed stack is returned and then execute the following:

# Assuming stack reversal for the rest of the books is already completed
# The bottom of the reversed stack should be the next node of the hold out
# To put the hold-out node to the bottom,
# we make the orignal "next node" point to the hold out,
# and cut off hold out's original pointer to avoid cyclic link
head.next.next = head
head.next = None

Putting these together, we get the following recursive implementation:

class RecursiveSolution:
    def reverseList(self, head: ListNode) -> ListNode:
        # Base case: when we only have one node, or when given empty list,
        #   return `head` directly
        if head is None or head.next is None:
            return head

        # Recursive call to reverse rest of the stack excluding
        # the head of the current function call
        reverse_rest = self.reverseList(head.next)

        # Only execute the remaining when the returned stack
        #   is already reversed
        head.next.next = head
        head.next = None

        return reverse_rest

Time and space complexity

• O(n) space complexity: Recursion involves call stack that must take up space equal to the depth of the recursion
• O(n) time complexity: We need n recursive calls to complete the reversal

where n is the number of nodes in the singly linked list.

Example unit tests (pytest)

import pytest


class Helper:
    """Helper class for easier handling of linked list"""
    @staticmethod
    def linked_list_to_array(head):
        array = []
        current = head
        while current:
            array.append(current.val)
            current = current.next

        return array

    @staticmethod
    def array_to_linked_list(array):
        head = ListNode(array[0])
        current = head
        for item in array[1:]:
            current.next = ListNode(item)
            current = current.next

        return head


# Stackover flow reference for passing argument to pytest fixture:
#   https://stackoverflow.com/a/44701916/3969516
@pytest.fixture
def test_input_linked_list():
    def _method(array):
        return Helper.array_to_linked_list(array)

    return _method

def test_reverse_multiple_nodes(test_input_linked_list):
    assert Helper.linked_list_to_array(
        IterativeSolution().reverseList(
            test_input_linked_list([1, 2, 3, 4, 5])
        )
    ) == [5, 4, 3, 2, 1]
    assert Helper.linked_list_to_array(
        RecursiveSolution().reverseList(
            test_input_linked_list([1, 2, 3, 4, 5])
        )
    ) == [5, 4, 3, 2, 1]


def test_reverse_empty_list():
    assert IterativeSolution().reverseList(None) is None
    assert RecursiveSolution().reverseList(None) is None


def test_reverse_single_node():
    head = Helper.array_to_linked_list([1])
    assert Helper.linked_list_to_array(
        IterativeSolution().reverseList(head)
    ) == [1]
    assert Helper.linked_list_to_array(
        RecursiveSolution().reverseList(head)
    ) == [1]

Other useful references

For recursion, I prefer thinking about call stack and considering that we have different head in each recursive call. For a fun video that is worth revisiting periodically — Computerphile provides a great explanation of recursion from the perspective of the call stack, which is linked here.