The problem
Implement a perform reverse_list that takes a singly-linked listing of nodes and returns an identical listing within the reverse order.
Assume the presence of a category Node, which exposes the property worth/Worth and subsequent/Subsequent. subsequent should both be set to the subsequent Node within the listing, or to None (or null) to point the tip of the listing.
To help in writing checks, a perform make_linked_list (Node.asLinkedList() in Java) has additionally been outlined, which converts a python listing to a linked listing of Node.
The ultimate checks will use a really lengthy listing. Bear in mind {that a} recursive resolution will run out of stack.
The answer in Python code
Choice 1:
def reverse_list(node):
res = None
whereas node:
res = Node(node.worth, res)
node = node.subsequent
return res
Choice 2:
def reverse_list(head):
tail = None
whereas head:
tail, head.subsequent, head = head, tail, head.subsequent
return tail
Choice 3:
def reverse_list(node):
earlier = None
whereas node:
earlier, node, earlier.subsequent = node, node.subsequent, earlier
return earlier
Take a look at instances to validate our resolution
# create linked lists for testing by chaining nodes
take a look at.assert_equals(reverse_list(Node(1, Node(2, Node(3, None)))), Node(3, Node(2, Node(1, None))))
# or alternately use the helper perform
take a look at.assert_equals(reverse_list(make_linked_list([1, 2, 3, 4, 5])), make_linked_list([5, 4, 3, 2, 1]))