Reorder Linked List in Zigzag Halves
medium
Linked ListFast Slow PointersIn Place Mutation
Asked atAmazonMicrosoftGoogleMetaLinkedin
Problem Description
Given the head of a singly linked list with nodes `n0 → n1 → n2 → … → n(k-1) → nk`, reorder it **in-place** to follow this pattern:
```
n0 → nk → n1 → n(k-1) → n2 → n(k-2) → …
```
In other words, interleave the first half of the list with the **reversed** second half. You may **not** create new nodes — only modify `next` pointers.
**Example 1:**
```
Input: [2, 4, 6, 8, 10]
Output: [2, 10, 4, 8, 6]
```
**Example 2:**
```
Input: [1, 3, 5, 7]
Output: [1, 7, 3, 5]
```
Constraints
- The number of nodes is in the range [1, 5 * 10^4].
- Node values are in the range [1, 10^5].
- You must modify the list in-place without allocating new nodes.
Follow-up
Extend the solution to support a doubly linked list, maintaining both `prev` and `next` pointers correctly throughout the reorder.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.