Fold the Chain
MediumLinked List
Problem
Imagine folding a paper strip in half so the far end lands next to the start. For a list L0 → L1 → … → Ln-1, the folded order is L0 → Ln-1 → L1 → Ln-2 → L2 → ….
Given the head, rearrange the nodes (not just the values) into the folded order and return the head.
Example 1
- Input:
- head = [1, 2, 3, 4, 5]
- Output:
- [1, 5, 2, 4, 3]
First, last, second, second-to-last, then the middle.
Example 2
- Input:
- head = [1, 2, 3, 4]
- Output:
- [1, 4, 2, 3]
Constraints
- 0 ≤ number of nodes ≤ 5 · 10^4
- 1 ≤ node.val ≤ 1000
- Use O(1) extra space.
Hint
Show the first hint
The folded order alternates between the front half read forwards and the back half read backwards.
Walkthrough
How to approach it
01Clarify before coding
- Move nodes or values? Nodes; values must stay attached to their nodes.
- For odd lengths, where does the middle go? At the very end.
- Is extra memory allowed? Aim for O(1).
02Brute force
Store all nodes in an array, then relink them with two indices i (from the front) and j (from the back).
Cost: O(n) time and O(n) extra space for the array: simple, but the constant-space version is the expected answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.