Sunday, February 26, 2023
HomeSoftware EngineeringLearn how to Reverse a singly-linked listing in Python

# Learn how to Reverse a singly-linked listing in Python

## 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
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]))
``````
RELATED ARTICLES