Odd Even Linked List Complexity Analysis

def oddEvenList(head):                    # O(1)
    if not head or not head.next: return head  # O(1)
    
    odd = head                              # O(1)
    even = head.next                        # O(1)
    
    while even and even.next:              # ← LOOP: ⌊n/2⌋ iterations
        odd.next = even.next               # O(1)
        even.next = odd.next               # O(1)
        odd = odd.next                     # O(1)
        even = even.next                   # O(1)
    
    odd.next = evenHead                    # O(1)
    return oddHead                         # O(1)

# n=5: 1→2→3→4→5
# Iteration 1: even=2, even.next=3 ✓
# Iteration 2: even=4, even.next=5 ✓
# Iteration 3: even=5, even.next=None ✗
# Total iterations: 2 = ⌊5/2⌋ = O(n)

# n=6: 1→2→3→4→5→6
# Iterations: 3 = ⌊6/2⌋ = O(n)

# General formula: iterations = ⌊n/2⌋ = Θ(n)

Variables (Fixed count):
odd      → ListNode pointer
even     → ListNode pointer
evenHead → ListNode pointer

Total: 3 pointers = O(1)

No recursion → No call stack growth
No arrays → No dynamic allocation
In-place → Modifies existing nodes only

Input:     1→2→3→4→5
Memory:     ↑  ↑
           odd even

n=5:  [odd,even,evenHead] = 3 pointers
n=1M: [odd,even,evenHead] = 3 pointers

Space Growth: Constant = O(1)

| Approach | Time | Space | Method |
|----------|------|-------|--------|
| **Optimal** | **O(n)** | **O(1)** | Two pointers |
| Array | O(n) | **O(n)** | Copy to array |
| Recursion | O(n) | **O(n)** | Call stack |
| Reverse Groups | O(n) | O(1) | Multiple reverses |

**Interviewer: 'Time/space complexity?'**

"Time: O(n) single pass - each node visited once
 Space: O(1) constant - only 3 pointers

The while loop runs ⌊n/2⌋ times. Each iteration
performs constant time pointer operations.

We don't use recursion (no call stack) or extra
data structures - purely in-place manipulation."

Let T(n) = time complexity

T(n) = ⌊n/2⌋ × c + d    where c,d = constants
     = (n/2 - r) × c + d  where r < 1
     = (c/2)n - rc + d
     = O(n)

Space S(n) = 3 pointers
          = O(1)

import time

def measure_complexity(n):
    head = create_list(list(range(n)))
    start = time.time()
    oddEvenList(head)
    return time.time() - start

# n=10³: 0.001s, n=10⁶: 1.2s → Linear!