Reorder List | CodeTutor

Reorder List

Medium

Linked Lists Two Pointers Fast & Slow Pointers LinkedList In-Place Reversal

Problem

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln-1 → Ln

Reorder the list to be on the following form:

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

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

Constraints

The number of nodes in the list is in the range [1, 5 * 10^4]
1 <= Node.val <= 1000

Examples

Input: head = [1,2,3,4]

Output: [1,4,2,3]

The original list is 1→2→3→4. After reordering: take the first node (1), then the last node (4), then the second node (2), then the second-to-last node (3). Result: 1→4→2→3.

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

Output: [1,5,2,4,3]

The original list is 1→2→3→4→5. After reordering: 1 (first), 5 (last), 2 (second), 4 (second-to-last), 3 (middle). Result: 1→5→2→4→3.

Loading Python...