Sort the list

Problem

A linked list of order totals is in random order. Sort it in ascending order using only node operations (no sorting of a Python list) and print the result.

Input, output and limits

Input: One line of integers separated by spaces.
Output: The sorted values separated by spaces.
Constraints: 1 ≤ number of values ≤ 10000
1 ≤ each value ≤ 1000000000

Examples

Example

Input

4 2 9 1 7

Output

1 2 4 7 9

Hints

Try the problem first. Open one hint at a time.

Hint 1

Merge sort works well: split at the middle, sort each half, merge.

Hint 2

Cut the first half off with slow.next = None before sorting it.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Reverse in groups of khard
Rotate right by khard
Where does the loop start?hard
Reorder the listhard
Odd positions, then even positionsmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Linked Lists problems

Problem

Input, output and limits

Examples

Hints

More Linked Lists problems