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):

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
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

## 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):
self.assertListEqual(values, [])

def test_one_node(self):
self.assertListEqual(values, )

def test_multiple_nodes(self):
self.assertListEqual(values, [4, 3, 2, 1])

def test_double_reversal(self):
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):
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.