0143.Reorder List

• Link: 143. Reorder List - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a singly linked list:
  • L0 -> L1 -> L2 -> ... -> Ln
• Reorder it in place into:
  • L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
• We cannot modify node values. We must relink the existing nodes.

Edge Case

• empty list or one node: no change needed
• two nodes: already in the correct order
• odd length:
  • one middle node remains at the end after merging
• even length:
  • the list splits evenly into two halves
• we must cut the list into two parts before merging, otherwise it is easy to create a cycle

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Find middle + reverse second half + merge	$O(n)$	$O(1)$

Method 1 - Find middle + reverse second half + merge

Approach

• This problem is a combination of 3 standard linked-list operations.

1. Find the middle

   • Use slow/fast pointers.
   • When the loop ends, slow is at the middle.

2. Reverse the second half

   • Start from slow.next
   • Cut the list first with slow.next = None
   • Reverse the second half in place

3. Merge the two halves

   • First half: L0 -> L1 -> L2 -> ...
   • Reversed second half: Ln -> Ln-1 -> ...
   • Alternate nodes from the two lists

Why this works

• The final order always alternates:
  • one node from the front
  • one node from the back
• Reversing the second half gives the back nodes in exactly the order we need.
• Then we zip the two halves together one node at a time.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Code

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
 
        # 1) Find middle
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
 
        # 2) Reverse second half
        second = slow.next
        slow.next = None
 
        prev = None
        cur = second
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
 
        # 3) Merge two halves
        first, second = head, prev
        while second:
            tmp1 = first.next
            tmp2 = second.next
 
            first.next = second
            second.next = tmp1
 
            first = tmp1
            second = tmp2

---

Mistake

• Forgetting slow.next = None
  • If the first half is not disconnected before merging, the old pointers can create a cycle.
• Reversing from slow instead of slow.next
  • That incorrectly includes the middle node in the second half.
• Losing the remaining nodes during merge
  • Save tmp1 and tmp2 before rewiring next, otherwise part of the list gets disconnected.