Reorder List

Problem

https://leetcode.com/problems/reorder-list/

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.

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 number of nodes in the list is in the range [1, 5 * 10:sup:`4`].
1 <= Node.val <= 1000

Pattern

Linked List, Two Pointers, Stack, Recursion

Approaches

Two Pointers

Explanation

While reordering a linked list is hard, doing the same reordering for an array is easy. First, we copy all the linked list nodes into an array. Then we use two pointers i and j, starting from the beginning and end of the array, and set nodes[i].next to nodes[j], and nodes[j].next to nodes[i + 1]. We stop when the two pointers meet. Finally, we set the next pointer of the last node to None.

Code

from __future__ import annotations


class ListNode:
    """Node in a linked list."""

    def __init__(self, val: int = 0, next: ListNode | None = None):
        self.val = val
        self.next = next

    @classmethod
    def from_list(cls, vals: list[int]) -> ListNode | None:
        dummy = cls(0)
        node = dummy
        for val in vals:
            node.next = cls(val)
            node = node.next
        return dummy.next

    def to_list(self) -> list:
        result = []
        node = self
        while node:
            result.append(node.val)
            node = node.next
        return result


def reorderList(head: ListNode | None) -> None:
    """Reorder ``head`` in-place by interleaving front and back."""
    nodes = []
    node = head
    while node:
        nodes.append(node)
        node = node.next

    i = 0
    j = len(nodes) - 1
    while i < j:
        nodes[i].next = nodes[j]
        i += 1
        if i >= j:
            break
        nodes[j].next = nodes[i]
        j -= 1

    nodes[i].next = None

Test

>>> from reorder_list__two_pointers import reorderList, ListNode
>>> head = ListNode.from_list([1, 2, 3, 4])
>>> reorderList(head)
>>> head.to_list()
[1, 4, 2, 3]
>>> head = ListNode.from_list([1, 2, 3, 4, 5])
>>> reorderList(head)
>>> head.to_list()
[1, 5, 2, 4, 3]

Complexity

\(n\) is the number of nodes

Measure	Complexity	Notes
Time	\(O(n)\)	one pass through the original linked list, and one pass through the array
Auxiliary Space	\(O(n)\)	array

class reorder_list__two_pointers.ListNode(val: int = 0, next: ListNode | None = None)

Bases: object

Node in a linked list.

classmethod from_list(vals: list[int]) → ListNode | None

to_list() → list

reorder_list__two_pointers.reorderList(head: ListNode | None) → None: Reorder head in-place by interleaving front and back.

Split And Merge

Explanation

Note the reordering keeps the first half of the list in the original order and reversed the second half of the list. Thus, we can reorder the linked list by splitting it into two halves, reversing the second half, and merging the two halves together.

Find the middle of the linked list using the slow and fast pointer technique. We start fast = head.next which means it is always at index \(2i + 1\) when slow is at index \(i\). This means for even length lists, slow will be the first middle node instead of the second middle node.
Reverse the second half of the linked list. Starting from slow, we reverse the linked list by setting slow.next to prev (initially None), then moving prev = slow and slow = original_slow_next. This splits the linked list into two halves.
```
1 -> 2 -> 3 -> 4 -> None
```
becomes
```
1 -> 2 -> None
4 -> 3 -> 2 -> None
```
Note that the first reversal slow.next = None is what cuts the linked list into 2 halves.
Merge the two halves together. Starting from the head of the first half (head) and the head of the reversed second (where prev ends), we merge the two halves by setting head.next = prev and prev.next = original_head_next, then moving head and prev to their original next values.

The reason for fast = head.next becomes clear now. For an even length list, the first half has one less node than the second half. Thus, we go 1 -> 4 -> 2 -> 3 -> None. Had we started fast = head, the split would be

1 -> 2 -> 3 -> None
4 -> 3 -> None

which would result in 1 -> 4 -> 2 -> 3 -> 3 -> ..., which is incorrect.