Odd Even Linked List Rearrangement

Given head of singly linked list, group all odd-indexed nodes together followed by even-indexed nodes. Return reordered list.

Index 1 = odd, Index 2 = even, Index 3 = odd, etc. Original relative order within odd/even groups preserved.

              
Python

          Example transformation
        
# Input:  1 -> 2 -> 3 -> 4 -> 5
# Output: 1 -> 3 -> 5 -> 2 -> 4

ListNode Class & Utilities

              
            
Python

          Standard setup for testing
        
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def create_list(values):
    dummy = ListNode(0)
    curr = dummy
    for val in values:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Optimal Solution - Single Pass O(n)

              
            
Python

          Two pointer separation - Interview Favorite
        
def oddEvenList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    # oddHead/odd = first odd node (index 1), third (index 3), etc.
    oddHead = odd = head
    # evenHead/even = second even node (index 2), fourth (index 4), etc.
    evenHead = even = head.next
    
    while even and even.next:
        # Connect odd -> next odd
        odd.next = even.next
        odd = odd.next
        
        # Connect even -> next even
        even.next = odd.next
        even = even.next
    
    # Connect end of odds to start of evens
    odd.next = evenHead
    
    return oddHead

# Test cases
input1 = create_list([1,2,3,4,5])
print(print_list(oddEvenList(input1)))  # [1,3,5,2,4]

input2 = create_list([2,1,3,5,6,4,7])
print(print_list(oddEvenList(input2)))  # [2,3,6,7,1,5,4]

**Time: O(n)** | **Space: O(1)** - Single pass, in-place modification

Step-by-Step Visualization

              
            
Python

          Input: 1->2->3->4->5
        
# Initial: odd=1, even=2
# Iteration 1:
# odd.next = 3, odd = 3
# even.next = 4, even = 4

# Current: 1->3  and  2->4->5

# Iteration 2:
# odd.next = 5, odd = 5
# even.next = None (end)

# Final: 1->3->5->2->4

Alternative: Dummy Node Approach

              
            
Python

          More explicit but same complexity
        
def oddEvenListDummy(head: ListNode) -> ListNode:
    if not head:
        return None
    
    oddDummy = odd = ListNode(0)
    evenDummy = even = ListNode(0)
    
    isOdd = True
    curr = head
    while curr:
        if isOdd:
            odd.next = curr
            odd = odd.next
        else:
            even.next = curr
            even = even.next
        curr = curr.next
        isOdd = not isOdd
    
    odd.next = evenDummy.next
    even.next = None
    return oddDummy.next

Edge Cases Handled

Empty list → returns None
Single node → returns unchanged
Two nodes → [1,2] → [1,2]
Odd length → works correctly
Even length → works correctly

              
            
Python

          Complete test suite
        
def test_odd_even_list():
    # Edge cases
    assert print_list(oddEvenList(None)) == []
    assert print_list(oddEvenList(create_list([1]))) == [1]
    assert print_list(oddEvenList(create_list([1,2]))) == [1,2]
    
    # Normal cases
    assert print_list(oddEvenList(create_list([1,2,3,4,5]))) == [1,3,5,2,4]
    print('✅ All tests passed!')

test_odd_even_list()

Interview Explanation Template

1. Clarify: 1-indexed? Preserve relative order?
2. Brute force: Array → O(n) space
3. Optimal: Two pointers separating odd/even chains
4. Complexity: O(n) time, O(1) space
5. Walk through: Show pointer movement on paper
6. Code: Dummy nodes or direct manipulation
7. Test: Edge cases + normal case

Common Mistakes to Avoid

Forgetting `even.next = None` at end
Wrong indexing (0-based vs 1-based)
Not handling odd-length lists
Breaking original relative order
Extra space usage (array approach)

VS Code Debugging Setup

              
            
JSON

          launch.json configuration
        
{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "Odd Even Linked List",
      "type": "python",
      "request": "launch",
      "program": "${file}",
      "console": "integratedTerminal"
    }
  ]
}

Set breakpoints on `odd.next` and `even.next` lines, press F5 to visualize pointer movement!

Interview Variations

Rearrange by node values even/odd instead of positions
Alternate even-odd values after rearrangement
K-group odd-even rearrangement
Cycle detection with odd-even pointers

Key Takeaways

Pattern: Split linked list into two chains, then reconnect. Classic two-pointer manipulation.

Pro Tip: Always draw the before/after diagram during interviews to show understanding.

**Copy this solution to VS Code, add breakpoints, and practice explaining it aloud!**