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, ) 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
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.