Reorder linked list.
Medium
Unlock detailed company stats for this questionUpgrade
You're given the head of a singly linked list L0 → L1 → ... → Ln-1 → Ln. Reorder it in place to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ....
Change the links between nodes rather than the values stored in them. The function doesn't return anything.
Example 1
Input: head = [1, 2, 3, 4] Output: [1, 4, 2, 3]
Example 2
Input: head = [1, 2, 3, 4, 5] Output: [1, 5, 2, 4, 3]
Constraints
- The list has between
1and5 * 10^4nodes. 1 <= Node.val <= 1000
Approach
The reordered list alternates between nodes from the front and nodes from the back. You can't walk a singly linked list backward, but you can reverse its back half, after which both halves read in the order you need. That gives three steps, each O(n). First, find the middle with a slow pointer that moves one node at a time and a fast pointer that moves two. Second, reverse everything after the middle and cut it off from the front half. Third, weave the halves together, taking one node from each in turn.
Steps
- Move
slowone node andfasttwo nodes at a time untilfastcan't move two more.slowis now at the end of the first half. - Reverse the list that starts at
slow.next, then setslow.nextto empty. - Walk the first half and the reversed second half together, linking a node from the first half to a node from the second half, then to the next node from the first half.
Complexity
- Time:
O(n). Each step is a single pass. - Space:
O(1). The nodes are relinked in place.
Common mistakes
- Not cutting the first half off from the second. If the middle node still points into the reversed half, the merge creates a cycle.
- Swapping values instead of relinking nodes. The task asks you to change the links.
Related courses
Course
Course
Course