Reversing a linked list is a popular technical interview question and one I see a lot on popular programming challenge websites. The programming challenge typically has a custom LinkedList Class with a Reverse Method that the developer needs to complete to properly reverse a linked list. A Node Class is provided that represents each node in the linked list, and the LinkedList Class has a pointer to the head node. Let's solve this programming challenge in Python so we can solve it for our next technical job interview.

Python Node Class for Linked List

Here is a simple Python Node Class we will be using to represent each node in the linked list. Each node in the linked list contains an integer as a value and a pointer to the next node. The __repr__ method is a bit different from my other tutorials as it only returns the value of the node. This is done to simplify unit testing.

class Node(object):
    def __init__(self, value: int, next_node: "Node" = None):
        self.value = value
        self.next = next_node

    def __repr__(self):
        return self.value

Custom Python LinkedList Class

Typically the programming challenge provides a custom LinkedList Class with a member variable, called head, that points to the head node of the linked list. The class also contains an empty reverse method that needs to be completed by the developer.

class LinkedList(object):
    def __init__(self, head: Node = None):
        self.head = head

    def reverse(self) -> None:
        # Write the Algorithm

Reverse Linked List in Python

Now let's code the algorithm to reverse the linked list in Python.

First, if the linked list is empty, let's not go any further. We don't need to waste any cycles reversing an empty linked list.

Next, we need to loop through the nodes in the linked list and modify their next pointers so that they point to the previous node in the current loop as opposed to the next node. To do this, we track 3 nodes as we iterate through the list: previous node, current node, and next node. We will stop looping when we have reached the last node in the linked list.

When we have reached the last node in the linked list, we set it as the new head node and adjust its next pointer to point to the previous node.

def reverse(self) -> None:
    if self.head is None:
        return

    previous_node = None
    current_node = self.head
    next_node = current_node.next

    while next_node is not None:
        current_node.next = previous_node
        previous_node = current_node
        current_node = next_node
        next_node = current_node.next

    self.head = current_node
    self.head.next = previous_node

Unit Tests for Reversing Linked List

Let's use Python's Unit Testing Framework to test the reverse method of the LinkedList Class. We will test it for an empty linked list, linked list with only 1 node, and a linked list with multiple node. Let's also test to make sure calling reverse on a linked list twice returns the original linked list. Here is a test case with the 4 unit tests.

class LinkedListTests(unittest.TestCase):
    def test_empty_list(self):
        linked_list = LinkedList()
        linked_list.reverse()
        values = list(linked_list)
        self.assertListEqual(values, [])

    def test_one_node(self):
        linked_list = LinkedList(Node(1))
        linked_list.reverse()
        values = list(linked_list)
        self.assertListEqual(values, [1])

    def test_multiple_nodes(self):
        linked_list = LinkedList(Node(1, Node(2, Node(3, Node(4)))))
        linked_list.reverse()
        values = list(linked_list)
        self.assertListEqual(values, [4, 3, 2, 1])

    def test_double_reversal(self):
        linked_list = LinkedList(Node(1, Node(2, Node(3, Node(4)))))
        linked_list.reverse()
        linked_list.reverse()
        values = list(linked_list)
        self.assertListEqual(values, [1, 2, 3, 4])

To make the testing easier, I coded an iterator for the LinkedList Class. The iterator allows us to call list(linked_list) to get a list of values in proper order in the linked list. We will compare that list of values to the expected list of values in our unit tests.

def __iter__(self):
    current_node = self.head
    while current_node is not None:
        yield current_node.value
        current_node = current_node.next

Of course, we also need to make sure we add import unittest to the top of the Python file.

For convenience I also kick off the unit tests whenever someone runs the Python script.

if __name__ == '__main__':
    unittest.main(verbosity=2)

Running the unit tests will produce something like the following.

$ python main.py

test_double_reversal (__main__.LinkedListTests) ... ok
test_empty_list (__main__.LinkedListTests) ... ok
test_multiple_nodes (__main__.LinkedListTests) ... ok
test_one_node (__main__.LinkedListTests) ... ok

----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK

Process finished with exit code 0

Conclusion

We covered a lot of concepts in this tutorial and wrote a fair amount of code. The algorithm for reversing a linked list is pretty simple once you understand how it works. The additional code we wrote to 1) create an iterator for the LinkList Class and 2) test the algorithm using the Python Unit Testing Framework was fun and useful. I hope this helps you when you come across this question during a technical job interview or programming challenge.

Posted by David Hayden

David Hayden is a freelance web developer. In his spare time he tutors students on a wide variety of computer science topics and programming languages. You can find him on twitter as @koderdojo.

Related Posts: