Problem Description

You are given the head of a singly linked list. Your task is to reorganize the list by grouping all nodes at odd positions together, followed by all nodes at even positions, and return the reordered list.

The position counting starts from 1, so:

• The 1st node (position 1) is considered odd
• The 2nd node (position 2) is considered even
• The 3rd node (position 3) is considered odd
• And so on...

The key requirements are:

• Maintain the relative order within each group (odd nodes stay in their original order relative to each other, same for even nodes)
• Use O(1) extra space (modify the list in-place without creating new nodes)
• Achieve O(n) time complexity (single pass through the list)

For example, if the input list is 1 -> 2 -> 3 -> 4 -> 5:

• Odd position nodes: 1 (pos 1), 3 (pos 3), 5 (pos 5)
• Even position nodes: 2 (pos 2), 4 (pos 4)
• Output: 1 -> 3 -> 5 -> 2 -> 4

The solution uses two pointers to track the tail of odd and even sublists separately. As we traverse the list, we alternately append nodes to the odd and even sublists. Finally, we connect the tail of the odd sublist to the head of the even sublist to form the complete reordered list.

Intuition

The key insight is that we need to separate the linked list into two sublists - one containing nodes at odd positions and another containing nodes at even positions - then connect them together.

Since we need O(1) space, we cannot create new nodes or use additional data structures. We must rearrange the existing nodes by modifying their pointers.

Think of it like dealing cards into two piles alternately. If we have cards numbered 1, 2, 3, 4, 5, we'd deal them as:

• Pile 1 (odd): 1, 3, 5
• Pile 2 (even): 2, 4

The challenge is doing this with a linked list where we can only access nodes sequentially.

The natural approach is to maintain two separate chains while traversing:

1. An "odd chain" that links all odd-positioned nodes
2. An "even chain" that links all even-positioned nodes

As we traverse the original list, we can "pluck out" nodes and attach them to their respective chains. We need:

• Pointer a to track the tail of the odd chain
• Pointer b to track the tail of the even chain
• Pointer c to remember the head of the even chain (so we can connect it to the odd chain's tail at the end)

The pattern emerges: starting from the first node (odd), we alternately redirect pointers:

• Connect current odd node to the next odd node (skipping the even one in between)
• Connect current even node to the next even node (skipping the odd one in between)

This way, we're essentially "unweaving" the original list into two separate strands, then joining them end-to-end. The beauty is that this maintains the relative order within each group naturally, since we're processing nodes in their original sequence.

Solution Approach

Let's walk through the implementation step by step using the two-pointer technique to separate odd and even positioned nodes.

Initial Setup:

• First, handle the edge case: if head is None, return None
• Set pointer a to point to the first node (head) - this will track the tail of odd nodes
• Set pointer b to point to the second node (head.next) - this will track the tail of even nodes
• Save pointer c pointing to head.next - this preserves the head of the even nodes list for later connection

Main Loop: The loop continues while b and b.next exist. The condition b and b.next ensures we have enough nodes to continue the rewiring process.

In each iteration:

1. Connect odd nodes:

   • a.next = b.next - Make the current odd node point to the next odd node (skipping the even node in between)
   • a = a.next - Move the odd pointer forward to the newly connected node

2. Connect even nodes:

   • b.next = a.next - Make the current even node point to the next even node (after the odd node we just moved to)
   • b = b.next - Move the even pointer forward to the newly connected node

Example walkthrough with list 1 -> 2 -> 3 -> 4 -> 5:

Initial state:

• a points to node 1, b points to node 2, c points to node 2

Iteration 1:

• a.next = b.next → Node 1 now points to node 3
• a = a.next → a moves to node 3
• b.next = a.next → Node 2 now points to node 4
• b = b.next → b moves to node 4

Iteration 2:

• a.next = b.next → Node 3 now points to node 5
• a = a.next → a moves to node 5
• b.next = a.next → Node 4 now points to None (end of list)
• b = b.next → b becomes None

Loop ends as b is None.

Final Connection:

• a.next = c - Connect the tail of the odd list (node 5) to the head of the even list (node 2)
• Return head which still points to node 1

The final list structure is: 1 -> 3 -> 5 -> 2 -> 4

Time and Space Complexity:

• Time: O(n) - We traverse the list once
• Space: O(1) - We only use a constant number of pointers

Example Walkthrough

Let's trace through the algorithm with a simple example: 1 -> 2 -> 3 -> 4

Initial Setup:

Original: 1 -> 2 -> 3 -> 4
          ↑    ↑    
          a    b,c

• a points to node 1 (tracks odd nodes)
• b points to node 2 (tracks even nodes)
• c saves node 2 (head of even list)

Iteration 1:

Step 1: Connect odd nodes

a.next = b.next  // Node 1 points to node 3
1 -----> 3 -> 4
     2 ↗

Step 2: Move a forward

a = a.next  // a moves to node 3
1 -> 3 -> 4
     ↑
     a

Step 3: Connect even nodes

b.next = a.next  // Node 2 points to node 4
Odd chain:  1 -> 3
Even chain: 2 -> 4

Step 4: Move b forward

b = b.next  // b moves to node 4
Even chain: 2 -> 4
                 ↑
                 b

Check loop condition: b exists (node 4) but b.next is None, so loop ends.

Final Connection:

a.next = c  // Connect node 3 to node 2
Result: 1 -> 3 -> 2 -> 4

The nodes have been successfully reorganized with odd positions (1st and 3rd) followed by even positions (2nd and 4th), maintaining their relative order within each group.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. The algorithm traverses the entire linked list exactly once using the while loop. Each node is visited and processed with constant time operations (pointer reassignments), resulting in linear time complexity.

Space Complexity: O(1). The algorithm uses only a constant amount of extra space regardless of the input size. It maintains three pointers (a, b, and c) to rearrange the nodes in-place. No additional data structures are created that scale with the input size, making the space complexity constant.

Common Pitfalls

Pitfall 1: Not Preserving the Even List Head

One of the most common mistakes is forgetting to save a reference to the head of the even list before starting the rewiring process. If you don't store even_head = head.next at the beginning, you'll lose access to the even nodes after reorganizing the pointers.

Incorrect approach:

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return None
  
    odd_current = head
    even_current = head.next
    # Missing: even_head = head.next
  
    while even_current and even_current.next:
        odd_current.next = even_current.next
        odd_current = odd_current.next
        even_current.next = odd_current.next
        even_current = even_current.next
  
    # This will fail - we don't have reference to even list's head!
    odd_current.next = ???  # Lost reference to even nodes
  
    return head

Solution: Always save the head of the even list before modifying any pointers.

Pitfall 2: Incorrect Loop Condition

Another frequent error is using the wrong loop condition, which can lead to null pointer exceptions or incomplete processing.

Incorrect approaches:

# Wrong: Only checking even_current
while even_current:  # This can cause NullPointerException
    odd_current.next = even_current.next  # even_current.next might not exist
  
# Wrong: Only checking even_current.next
while even_current.next:  # Misses the case when even_current itself is None

Solution: Use while even_current and even_current.next: to ensure both the current even node and the next node exist before attempting to access even_current.next.

Pitfall 3: Forgetting Edge Cases

Failing to handle edge cases properly, particularly:

• Empty list (head is None)
• Single node list
• Two node list

Incorrect approach:

def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # Missing null check - will crash on empty list
    odd_current = head
    even_head = head.next  # NullPointerException if head is None
    even_current = head.next

Solution: Always check if head is None before accessing head.next. The algorithm naturally handles single and two-node lists correctly with the proper loop condition.

Pitfall 4: Incorrect Pointer Movement Order

Moving pointers in the wrong order or forgetting to move them can create infinite loops or incorrect connections.

Incorrect approach:

while even_current and even_current.next:
    # Forgetting to move odd_current forward
    odd_current.next = even_current.next
    # Missing: odd_current = odd_current.next
  
    even_current.next = odd_current.next  # This uses wrong odd_current position
    even_current = even_current.next

Solution: Always update pointers immediately after modifying their next references to maintain correct positions for the next iteration.