Challenge: Reverse a Linked List

Lab Python Intermediate 20 points

Build a linked list from the input, reverse it by changing the links (not by reversing the Python list), and print the values from the new head, separated by spaces.

Input

One line of values.

Output

The values in reversed order.

Example

Input

1 2 3 4

Output

4 3 2 1

Sample input available Sample output available

Editor

Python

Hints

Keep prev = None and cur = head.

In the loop: save cur.next, point cur.next at prev, then move prev and cur forward.

Solution explanation

Each arrow is turned around once: O(n) time and O(1) extra space.

Show solution

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


values = input().split()
head = None
for v in reversed(values):
    node = Node(v)
    node.next = head
    head = node
prev, cur = None, head
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
out = []
while prev:
    out.append(prev.value)
    prev = prev.next
print(" ".join(out))

Output

Answer