Reorder List

How it works

To reorder the list into the pattern L1 → Ln → L2 → Ln−1 → L3 → Ln−2 → ..., we can break the problem into three simple steps:

1. Find the middle of the linked list using slow and fast pointers. This splits the list into two halves.

2. Reverse the second half of the list. Doing this makes it easy to merge nodes from the front and back alternately.

3. Merge the two halves one-by-one: Take one node from the first half (first), then one from the reversed second half (second), and repeat.

This method is clean, intuitive, and uses only O(1) extra space.

Steps

1. Find the middle:

   • Use slow and fast pointers.
   • When fast reaches the end, slow will be at the midpoint.

2. Reverse the second half:

   • Start from slow.next.
   • Reverse it using the standard linked-list reversal approach with prev and tmp variables.

3. Merge the two lists:

   • Take a node from first half.
   • Take a node from the reversed second half.
   • Continue until second is exhausted.

This produces the desired reordered list in-place with no extra memory.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Incorrectly Finding the Middle Node

The slow/fast pointer technique must be initialized correctly. Starting both pointers at head versus starting fast at head.next affects whether slow ends at the last node of the first half or the first node of the second half. This off-by-one error leads to incorrect splitting and malformed results.

Forgetting to Disconnect the Two Halves

After finding the middle, you must set slow.next = None to split the list into two independent halves. Without this, the reversal step creates a cycle or corrupts the original list structure, causing infinite loops during merging.

Losing References During Merge

When interleaving nodes from the first and second halves, each next pointer reassignment breaks the original chain. Failing to save tmp1 = first.next and tmp2 = second.next before modifying pointers causes you to lose track of remaining nodes, resulting in an incomplete or broken list.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        prev = slow.next = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* second = slow->next;
        ListNode* prev = slow->next = nullptr;
        while (second != nullptr) {
            ListNode* tmp = second->next;
            second->next = prev;
            prev = second;
            second = tmp;
        }

        ListNode* first = head;
        second = prev;
        while (second != nullptr) {
            ListNode* tmp1 = first->next;
            ListNode* tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};