Leetcode - 143. Reorder List

Medium

Dec 23, 2025

#linked-list

143. 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]

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

Constraints:

Notes

Intuition

The reordering alternates between nodes from the start and end of the list. By reversing the second half and merging it with the first half, we can achieve this pattern in-place.

Implementation

Three steps, each O(n). First, find the midpoint using slow/fast pointers (fast starts at head.next). Second, reverse the second half starting at slow.next and break the link by setting slow.next = None. Third, merge by alternating: save next pointers for both halves, link first.next to second, link second.next to the saved first-next, then advance both pointers.

Edge-cases

The algorithm handles odd and even length lists naturally. The midpoint calculation ensures the first half is equal or one longer than the second.

Time: O(n) — three sequential O(n) passes
Space: O(1) — all operations done in-place

Complexity

Solution

from typing import Optional
from lcutils import ListNode

# 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:
        """
        Do not return anything, modify head in-place instead.
        """

        # Step 1: Find the mid-point (slow and fast) O(n)
        slow = head
        fast = head.next if head else None
        while fast and fast.next:
            slow = slow.next if slow else None
            fast = fast.next.next

        # Step 2: Reverse the second half O(n)
        second: Optional[ListNode] = None
        prev: Optional[ListNode] = None
        if slow:
            second = slow.next
            slow.next = None # break the link in the original list
            while second:
                temp = second.next
                second.next = prev
                prev = second
                second = temp

        # Step 3: Merge the two lists O(n)
        first, second = head, prev
        while first and second:
            temp1, temp2 = first.next, second.next
            first.next = second
            second.next = temp1
            first = temp1
            second = temp2




if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()