ammar@web:~$
~/leetcode/medium/reorder-list
Medium·[2025-12-23]

143. Reorder List

[#linked-list]

## description

## 143. Reorder List

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

plain text
1L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

plain text
1L0 → 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:

plain text
1Input: head = [1,2,3,4] 2Output: [1,4,2,3]

Example 2:

plain text
1Input: head = [1,2,3,4,5] 2Output: [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

          python
          1from typing import Optional 2from lcutils import ListNode 3 4# Definition for singly-linked list. 5# class ListNode: 6# def __init__(self, val=0, next=None): 7# self.val = val 8# self.next = next 9class Solution: 10 def reorderList(self, head: Optional[ListNode]) -> None: 11 """ 12 Do not return anything, modify head in-place instead. 13 """ 14 15 # Step 1: Find the mid-point (slow and fast) O(n) 16 slow = head 17 fast = head.next if head else None 18 while fast and fast.next: 19 slow = slow.next if slow else None 20 fast = fast.next.next 21 22 # Step 2: Reverse the second half O(n) 23 second: Optional[ListNode] = None 24 prev: Optional[ListNode] = None 25 if slow: 26 second = slow.next 27 slow.next = None # break the link in the original list 28 while second: 29 temp = second.next 30 second.next = prev 31 prev = second 32 second = temp 33 34 # Step 3: Merge the two lists O(n) 35 first, second = head, prev 36 while first and second: 37 temp1, temp2 = first.next, second.next 38 first.next = second 39 second.next = temp1 40 first = temp1 41 second = temp2 42 43 44 45 46if __name__ == "__main__": 47 # Include one-off tests here or debugging logic that can be run by running this file 48 # e.g. print(solution.two_sum([1, 2, 3, 4], 3)) 49 solution = Solution() 50
          --EOF--