54. Reorder List
Rearrange the list by taking the first node, then the last node, then the second node, then the second-to-last node, and continuing inward. Preserve the original node values.
Change next links rather than creating replacement nodes. Odd- and even-length lists have different middle boundaries, but each original node must appear exactly once.
Example 1
Input
N0(1)→N1(2)→N2(3)→N3(4)
Output
N0→N3→N1→N2→null
Explanation: Split after N1, reverse N2→N3 into N3→N2, then weave.
Example 2
Input
N0→N1→N2→N3→N4
Output
N0→N4→N1→N3→N2→null
Explanation: The first half has the extra middle node N2, which remains the final node.
Example 3
Input
N0(5)→N1(5)→N2(5)
Output
N0→N2→N1→null
Explanation: Checking only values would miss an implementation that never changes the links.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- Inputs may be null. Lists are acyclic unless this problem explicitly detects a cycle.
Hints
Hint 1
Can the desired order be written as alternating two simpler lists?
Hint 2
Split after the first-half tail, then reverse the shorter second half.
Hint 3
Save both successors, link first→second→nextFirst, and advance through the saved references.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Even split, reverse, and weave
[1,2,3,4]
["N0","N3","N1","N2"]