Odd Even Linked List

XXX. Odd Even Linked List

Linked List

Two Pointer

Problem Statement:

Given a singly linked list, group all nodes at odd positions followed by all nodes at even positions.

• First node is odd (position 1)
• Maintain relative ordering within groups
• Position based, not value based

Java Solution:

public ListNode oddEvenList(ListNode head) {
    if (head == null)
        return null;
    
    ListNode odd = head;             // Points to odd position nodes
    ListNode even = head.next;       // Points to even position nodes
    ListNode evenHead = even;        // Save start of even nodes
    
    // Process pairs of nodes
    while (odd.next != null && even.next != null) {
        odd.next = odd.next.next;    // Skip even node
        even.next = even.next.next;  // Skip odd node
        odd = odd.next;              // Move to next odd
        even = even.next;            // Move to next even
    }
    
    odd.next = evenHead;             // Connect odd list to even list
    
    return head;
}

Example:

For list 1->2->3->4->5:

• First iteration:
  • odd: 1->3
  • even: 2->4
• Second iteration:
  • odd: 1->3->5
  • even: 2->4->null
• Result: 1->3->5->2->4

Complexity:

Time Complexity: O(n), one pass through list
Space Complexity: O(1), constant extra space

Implementation Notes:

• **Key Steps**:
  • Save even list head for reconnection
  • Process nodes in pairs
  • Connect odd tail to even head
• **Edge Cases**:
  • Empty list handling
  • Single node list
  • Even/Odd length lists