How to Reverse a singly-linked list in Python

The challenge

Implement a function reverse_list that takes a singly-linked list of nodes and returns a matching list in the reverse order.

Assume the presence of a class Node, which exposes the property value/Value and next/Nextnext must either be set to the next Node in the list, or to None (or null) to indicate the end of the list.

To assist in writing tests, a function make_linked_list (Node.asLinkedList() in Java) has also been defined, which converts a python list to a linked list of Node.

The final tests will use a very long list. Be aware that a recursive solution will run out of stack.

The solution in Python code

Option 1:

def reverse_list(node): res = None while node: res = Node(node.value, res) node = return res
Code language: Python (python)

Option 2:

def reverse_list(head): tail = None while head: tail,, head = head, tail, return tail
Code language: Python (python)

Option 3:

def reverse_list(node): previous = None while node: previous, node, = node,, previous return previous
Code language: Python (python)

Test cases to validate our solution

# create linked lists for testing by chaining nodes test.assert_equals(reverse_list(Node(1, Node(2, Node(3, None)))), Node(3, Node(2, Node(1, None)))) # or alternately use the helper function test.assert_equals(reverse_list(make_linked_list([1, 2, 3, 4, 5])), make_linked_list([5, 4, 3, 2, 1]))
Code language: Python (python)
Notify of
Inline Feedbacks
View all comments