Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Odd Even Linked List

MEDIUMProblemSolveExternal Links

Description

Given the head of a singly linked list, rearrange the nodes so that all nodes at odd positions come first, followed by all nodes at even positions.

Positions are 1-indexed, meaning the first node is at position 1 (odd), the second node is at position 2 (even), the third node is at position 3 (odd), and so on.

The relative order of nodes within the odd group and within the even group must remain the same as in the original list. You must solve this problem using O(1) extra space and O(n) time.

Examples

Example 1

Input: head = [1, 2, 3, 4, 5]

Output: [1, 3, 5, 2, 4]

Explanation: The nodes at odd positions are 1 (pos 1), 3 (pos 3), and 5 (pos 5). The nodes at even positions are 2 (pos 2) and 4 (pos 4). We place all odd-positioned nodes first, then all even-positioned nodes, giving us [1, 3, 5, 2, 4].

Example 2

Input: head = [2, 1, 3, 5, 6, 4, 7]

Output: [2, 3, 6, 7, 1, 5, 4]

Explanation: Odd-positioned nodes are 2 (pos 1), 3 (pos 3), 6 (pos 5), and 7 (pos 7). Even-positioned nodes are 1 (pos 2), 5 (pos 4), and 4 (pos 6). Grouping odd positions first gives [2, 3, 6, 7, 1, 5, 4].

Example 3

Input: head = []

Output: []

Explanation: The list is empty, so there is nothing to rearrange. We return an empty list.

Constraints

  • The number of nodes in the linked list is in the range [0, 10^4]
  • -10^6 ≤ Node.val ≤ 10^6

Editorial

Brute Force

Intuition

The simplest way to think about this problem is to separate the task into two phases: first collect the values in the right order, then write them back into the list.

Imagine you have a line of people standing in positions 1 through n. You want to rearrange them so that everyone at an odd position stands before everyone at an even position, while preserving the relative order within each group. The easiest way is to walk through the line, write down the names of people at odd positions on one list and even positions on another list. Then you call them back in order: first the odd-position list, then the even-position list.

We do the same with the linked list: traverse it once and collect all odd-position values, then all even-position values into an auxiliary array. Then traverse the list again and overwrite node values from this array.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Step 1: Initialize two empty lists: oddValues = [], evenValues = []. Set position = 1, current = head (node with value 1).

Step 2: Position 1 is odd. Add value 1 to oddValues. oddValues = [1]. Move to next node.

Step 3: Position 2 is even. Add value 2 to evenValues. evenValues = [2]. Move to next node.

Step 4: Position 3 is odd. Add value 3 to oddValues. oddValues = [1, 3]. Move to next node.

Step 5: Position 4 is even. Add value 4 to evenValues. evenValues = [2, 4]. Move to next node.

Step 6: Position 5 is odd. Add value 5 to oddValues. oddValues = [1, 3, 5]. No more nodes.

Step 7: Combine: result = oddValues + evenValues = [1, 3, 5, 2, 4].

Step 8: Traverse the list again and overwrite each node's value with the corresponding value from result. The list becomes 1 → 3 → 5 → 2 → 4.

Brute Force — Collecting Odd and Even Position Values — Watch how we traverse the linked list, collecting values at odd and even positions into separate groups, then merge them to form the final ordering.

Algorithm

  1. Create two empty arrays: oddValues and evenValues
  2. Traverse the linked list, maintaining a position counter starting at 1
  3. For each node:
    • If position is odd, append its value to oddValues
    • If position is even, append its value to evenValues
    • Increment position
  4. Concatenate oddValues + evenValues into a single result array
  5. Traverse the linked list again, overwriting each node's value with the corresponding value from the result array
  6. Return the head of the modified list

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        
        vector<int> oddValues, evenValues;
        ListNode* curr = head;
        int position = 1;
        
        while (curr) {
            if (position % 2 == 1) {
                oddValues.push_back(curr->val);
            } else {
                evenValues.push_back(curr->val);
            }
            curr = curr->next;
            position++;
        }
        
        // Merge odd values followed by even values
        for (int val : evenValues) {
            oddValues.push_back(val);
        }
        
        // Overwrite list values
        curr = head;
        int idx = 0;
        while (curr) {
            curr->val = oddValues[idx++];
            curr = curr->next;
        }
        
        return head;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        odd_values = []
        even_values = []
        curr = head
        position = 1
        
        while curr:
            if position % 2 == 1:
                odd_values.append(curr.val)
            else:
                even_values.append(curr.val)
            curr = curr.next
            position += 1
        
        result = odd_values + even_values
        
        curr = head
        idx = 0
        while curr:
            curr.val = result[idx]
            idx += 1
            curr = curr.next
        
        return head
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        List<Integer> oddValues = new ArrayList<>();
        List<Integer> evenValues = new ArrayList<>();
        ListNode curr = head;
        int position = 1;
        
        while (curr != null) {
            if (position % 2 == 1) {
                oddValues.add(curr.val);
            } else {
                evenValues.add(curr.val);
            }
            curr = curr.next;
            position++;
        }
        
        oddValues.addAll(evenValues);
        
        curr = head;
        int idx = 0;
        while (curr != null) {
            curr.val = oddValues.get(idx++);
            curr = curr.next;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list twice — once to collect all values into the two arrays, and once to write the merged values back. Each traversal visits all n nodes exactly once, so the total time is O(n) + O(n) = O(n).

Space Complexity: O(n)

We use two auxiliary arrays (oddValues and evenValues) that together store all n node values. This requires O(n) additional space proportional to the number of nodes in the list.

Why This Approach Is Not Efficient

While the brute force approach achieves O(n) time complexity, it uses O(n) extra space to store all node values in auxiliary arrays. The problem explicitly requires O(1) extra space complexity.

The fundamental issue is that we are not taking advantage of the linked list's structure. In a linked list, we can rearrange nodes by simply changing their next pointers — we do not need to copy values at all. If we could directly re-link the odd-positioned nodes to each other and the even-positioned nodes to each other, we would avoid needing any extra storage.

The key insight: since a linked list allows us to rewire connections between nodes in constant time, we can maintain two separate chains (one for odd-positioned nodes, one for even-positioned nodes) and build them simultaneously as we traverse, then connect the odd chain's tail to the even chain's head. This eliminates the need for any auxiliary data structure.

Optimal Approach - In-Place Pointer Rearrangement

Intuition

Instead of collecting values into arrays, we can rearrange the nodes themselves by manipulating their next pointers directly.

Think of a group of children standing in a single-file line, numbered 1 through n. You want to rearrange them so that all odd-numbered children stand together, followed by all even-numbered children. Instead of pulling everyone out of line and forming new lines, you tell each odd-numbered child to hold hands with the next odd-numbered child (skipping the even one between them), and similarly for even-numbered children. Now you have two interleaved chains — one of odd-numbered children and one of even-numbered children. Finally, you connect the end of the odd chain to the beginning of the even chain.

In linked list terms, we maintain two pointers: odd starting at the first node and even starting at the second node. We also save the head of the even list (evenHead). At each step, we skip the even node to link odd nodes together, and skip the odd node to link even nodes together. After the traversal, we connect the last odd node to evenHead.

Step-by-Step Explanation

Let's trace through with head = [1, 2, 3, 4, 5]:

Step 1: Initialize odd = node(1) (position 1), even = node(2) (position 2). Save evenHead = node(2).
List: 1 → 2 → 3 → 4 → 5

Step 2: Link odd node past even: odd.next = even.next → node(1).next = node(3). Now odd chain: 1 → 3.
Advance odd to node(3).

Step 3: Link even node past odd: even.next = odd.next → node(2).next = node(4). Now even chain: 2 → 4.
Advance even to node(4).

Step 4: Link odd node past even: odd.next = even.next → node(3).next = node(5). Now odd chain: 1 → 3 → 5.
Advance odd to node(5).

Step 5: Link even node past odd: even.next = odd.next → node(4).next = null. Now even chain: 2 → 4 → null.
Advance even to null. Loop ends because even is null.

Step 6: Connect odd chain tail to even chain head: odd.next = evenHead → node(5).next = node(2).
Final list: 1 → 3 → 5 → 2 → 4.

In-Place Odd-Even Rearrangement — Watch how two pointers (odd and even) leapfrog through the list, re-linking nodes into separate odd and even chains, then connecting them at the end.

Algorithm

  1. If the list is empty or has fewer than 3 nodes, return it as-is (already trivially rearranged)
  2. Initialize:
    • odd = head (first node, position 1)
    • even = head.next (second node, position 2)
    • evenHead = even (save the start of the even chain for later connection)
  3. While even is not null AND even.next is not null:
    • odd.next = even.next (link current odd node to the next odd node, skipping the even node between them)
    • odd = odd.next (advance odd pointer to the newly linked node)
    • even.next = odd.next (link current even node to the next even node, skipping the odd node between them)
    • even = even.next (advance even pointer)
  4. Connect the end of the odd chain to the start of the even chain: odd.next = evenHead
  5. Return head

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        
        odd->next = evenHead;
        return head;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        odd = head
        even = head.next
        even_head = even
        
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        
        odd.next = even_head
        return head
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        
        odd.next = evenHead;
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the entire linked list exactly once. In each iteration of the while loop, we process two nodes (one odd, one even) and perform a constant number of pointer reassignments. With n nodes total, the loop runs approximately n/2 times, giving O(n) total time.

Space Complexity: O(1)

We use only three extra pointers (odd, even, evenHead) regardless of the input size. No auxiliary arrays, hash maps, or other data structures are needed. The rearrangement is done entirely in-place by re-linking existing nodes.