Description
Reverse the links of a singly linked list and return its new head. Examples show node values in traversal order.
Solution
def reverse_list(head):
previous = None
while head:
following = head.next
head.next = previous
previous, head = head, following
return previousExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,4,7]]- Output
[7,4,1]
The last node becomes the first.
Example 2
- Input
[[]]- Output
[]
An empty list stays empty.
Example 3
- Input
[[2]]- Output
[2]
One node points to null in either direction.
Approach
Save the next node before redirecting the current pointer toward the previous node.
Time & space
O(n) time; O(1) space. Here n is the input length.