The starter builds a linked list from the input. Complete reverse(head) so that it reverses the links and returns the new head; the program then prints the values in order.
What to build
A function that turns every link around.
Requirements
- Complete
reverse(head), returning the new head. - Change the links of the nodes rather than making new ones.
Input
The first line has n (1 to 1000). The second line has n whole numbers.
Output
The values after reversing, separated by spaces.
Constraints
n is from 1 to 1000.
Example
Input:
3
1 2 3
Output:
3 2 1
Why it works
Three variables are enough: the previous node, the current one, and the saved next node, which stops the rest of the list from being lost.
Examples
Example 1 · Input
3 1 2 3
Expected output
3 2 1
Example 2 · Input
2 10 20
Expected output
20 10
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep prev, current and next; point current.next back at prev.
Hint 2
Save current.next before you overwrite it.
Solution
Show one correct solution (try it yourself first)
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prev
n = int(input())
head = None
for v in reversed(input().split()):
head = Node(int(v), head)
head = reverse(head)
values = []
while head:
values.append(str(head.value))
head = head.next
print(" ".join(values))