What if instead of progressing through nodes from head to tail, we wanted to move from tail to head? We can reverse a linked list to make this the default traversal!
Let’s examine what we’ll need to reverse the linked list.
# a -> b -> c -> d reverse(linked_list) # d -> c -> b -> a
We reassign each node’s
.next property to the preceding node. For the head node, this means
.next points to
- write a function:
reverse()takes one argument, an instance of
- return an instance of
LinkedListwhich contains all the nodes from the input in reverse order.
Solve this problem, then try to optimize your solution. It’s possible to solve this with
O(N) time and
O(1) space complexity.
We detail our implementation in the hint.