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/Next. next 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:

1
2
3
4
5
6

def reverse_list(node):
    res = None
    while node:
        res = Node(node.value, res)
        node = node.next
    return res

Option 2:

1
2
3
4
5

def reverse_list(head):
    tail = None
    while head:
        tail, head.next, head = head, tail, head.next
    return tail

Option 3:

1
2
3
4
5

def reverse_list(node):
    previous = None
    while node:
        previous, node, previous.next = node, node.next, previous
    return previous

Test cases to validate our solution

1
2
3
4

# 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]))