Reorder List

medium

You are given the head of a singly linked list:

L0 → L1 → … → Ln-1 → Ln

Reorder it to:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You may not modify the values in the list's nodes — only the nodes themselves may be changed.

Test Cases

Copy an input into the main harness and Run to verify

Input

head = [1,2,3,4]

Expected Output

[1,4,2,3]

Input

head = [1,2,3,4,5]

Expected Output

[1,5,2,4,3]

Hint 1 — click to reveal

You need the last node, then the second-to-last, and so on — that is the reverse of the back half.

Hint 2 — click to reveal

Split at the middle, reverse the second half, then weave the two halves together.

Java Compiler