Problem Statement #

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

Example 1:

Input:  1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input:  2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Problem Analysis #

This is a classic linked list manipulation problem that tests your understanding of pointer management and list traversal. The challenge lies not in the complexity of the algorithm, but in carefully maintaining multiple pointers while rewiring the connections between nodes.

Key Insights #

The fundamental concept to grasp is that we’re reorganizing nodes based on their position (1st, 2nd, 3rd, etc.), not their values. The first node is odd, the second is even, the third is odd, and so on. Our goal is to maintain the relative order within each group while separating them.

Since we’re working with a singly linked list, each node only knows about its next neighbor. This means we need to be deliberate about how we traverse and reconnect nodes, as we can’t go backwards if we make a mistake.

Solution Approach #

The elegant solution involves maintaining two separate lists during traversal: one for odd-positioned nodes and one for even-positioned nodes. As we walk through the original list, we alternately add nodes to each list. Finally, we connect the tail of the odd list to the head of the even list.

Algorithm Breakdown #

1. Initialize pointers: We start with pointers to the first node (odd) and second node (even). We also save a reference to the head of the even list, as we’ll need it later to connect the two lists.

2. Traverse and separate: We iterate through the list, connecting odd nodes to odd nodes and even nodes to even nodes. The key is that each node’s next.next becomes its new next, effectively skipping over the alternate nodes.

3. Connect the lists: Once we’ve reached the end, we connect the last odd node to the head of the even list.

4. Terminate the even list: We set the last even node’s next pointer to null to properly terminate the list.

Edge Cases #

There are two important edge cases to handle:

• Empty list: If the input is null, we simply return null.
• Single node: If there’s only one node, it’s already properly arranged (one odd node, zero even nodes), so we return it as is.

These edge cases are important because our algorithm assumes at least two nodes exist to set up both the odd and even list heads.

Time and Space Complexity #

• Time Complexity: O(n) where n is the number of nodes. We traverse the list exactly once.
• Space Complexity: O(1) as we only use a constant amount of extra space for pointers, regardless of input size.

Implementation #

var oddEvenList = function(head) {
    if (head === null) { // no list
        return null;
    }
    if (head.next === null) { // one node
        return head;
    }
    
    let odd = head;
    let even = head.next;
    let evenHead = even;
    let cur = even;
    let count = 0;
    
    while (cur.next) {
        count++;
        cur = cur.next;
        if (count % 2 === 0) { // even
            even.next = cur;
            even = even.next;
        } else { // odd
            odd.next = cur;
            odd = odd.next;
        }
    }
    
    odd.next = evenHead;
    even.next = null;
    return head;
};

Alternative Approach (More Optimal) #

While the above solution works correctly, there’s a more elegant approach that doesn’t require a counter. Instead, we can leverage the structure of the linked list itself:

var oddEvenList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    
    let odd = head;
    let even = head.next;
    let evenHead = even;
    
    // While there are more nodes to process
    while (even !== null && even.next !== null) {
        odd.next = even.next;      // Connect odd to next odd
        odd = odd.next;             // Move odd pointer forward
        even.next = odd.next;       // Connect even to next even
        even = even.next;           // Move even pointer forward
    }
    
    odd.next = evenHead;  // Connect odd list to even list
    return head;
};

This approach is cleaner because:

1. No counter needed: We determine odd/even by the natural alternation in the list structure
2. Simpler loop condition: We only check if there are more nodes to process
3. More intuitive: Each iteration processes one odd node and one even node

How It Works Step by Step #

Let’s trace through Example 1: 1->2->3->4->5->NULL

Initial state:

• odd = 1, even = 2, evenHead = 2
• List: 1->2->3->4->5->NULL

Iteration 1:

• odd.next = 3 (skip 2)
• odd = 3
• even.next = 4 (skip 3)
• even = 4
• List structure: 1->3->5->NULL and 2->4->NULL (conceptually)

Iteration 2:

• odd.next = 5 (skip 4)
• odd = 5
• even.next = null (skip 5)
• even = null
• Loop exits

Final connection:

• odd.next = evenHead (5->2)
• Result: 1->3->5->2->4->NULL

Key Takeaways #

1. Pointer management is crucial: Linked list problems often come down to carefully tracking multiple pointers and understanding what each represents.

2. Draw it out: For linked list problems, sketching the list and pointer movements on paper can prevent errors.

3. In-place algorithms are elegant: This solution achieves O(1) space complexity by rearranging existing nodes rather than creating new ones.

4. Edge cases matter: Always consider empty lists, single-node lists, and two-node lists when working with linked lists.

5. Multiple approaches exist: While the counter-based solution works, the pointer-jumping approach is more idiomatic for linked list manipulation.

This problem is an excellent exercise for understanding how to manipulate linked list structure while maintaining data integrity. The skills practiced here—maintaining multiple pointers, rewiring connections, and thinking about list structure—are fundamental to many other linked list problems.