Log inSign up
mediumLeetCodeNot Started

Odd Even Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return *the reordered list*.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Example 1 · 5 Nodes:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
Explanation: Odd indices 1, 3, 5 (values 1, 3, 5) grouped together, followed by even indices 2, 4 (values 2, 4).

Example 2 · 7 Nodes:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]
Explanation: Odd index nodes (2, 3, 6, 7) followed by even index nodes (1, 5, 4).

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Unzip interleaved pointer chains simultaneously without losing node references.
  • Determine optimal while loop termination conditions (even && even.next).
  • Preserve relative stability inside partitioned subgroups.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Separating or grouping alternating elements of a linked list.
  • Strict O(1) auxiliary space and O(N) time requirements.
  • Index-based (not value-based) partition.

Algorithmic Decision Tree:

  • Remember evenHead = head.next at the start so we can connect odd.next = evenHead at the end.
  • Loop on even && even.next because the even pointer is always ahead of the odd pointer.

Connected Patterns:

Partition ListSplit Linked List in PartsReorder List

1. Brute Force — Array Storage & Value Rewriting

Intuition

Collect odd-indexed values in one array and even-indexed values in another. Concatenate the two arrays and write values back to the list.

Algorithm

  1. Step 1: Traverse list, append odd indexed values to odds, even to evens.
  2. Step 2: Combine: combined = odds + evens.
  3. Step 3: Traverse list again, assigning curr.val = combined[i].
  4. Step 4: Return head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* oddEvenList(ListNode* head) {
15 if (!head || !head->next) return head;
16 vector<int> odds, evens;
17 int idx = 1;
18 for (ListNode* c = head; c; c = c->next, idx++) {
19 if (idx % 2 == 1) odds.push_back(c->val);
20 else evens.push_back(c->val);
21 }
22
23 ListNode* curr = head;
24 for (int v : odds) { curr->val = v; curr = curr->next; }
25 for (int v : evens) { curr->val = v; curr = curr->next; }
26 return head;
27 }
28};
29
30int main() {
31 ListNode* h = new ListNode(1);
32 h->next = new ListNode(2);
33 h->next->next = new ListNode(3);
34 h->next->next->next = new ListNode(4);
35 h->next->next->next->next = new ListNode(5);
36
37 Solution sol;
38 ListNode* res = sol.oddEvenList(h);
39
40 cout << "Brute Force Odd-Even: ";
41 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Collects N values into arrays and writes them back in two passes.
  • Space complexity: O(N) — Allocates arrays of size N.

Why Brute Force Doesn't Scale:

Array allocations violate the O(1) space constraint and cause unnecessary heap allocations.

For N = 100,000 nodes, the in-place unzipping runs in <1ms with 0 extra memory.

2. Better — Two Dummy Lists with Parity Toggle

Intuition

Maintain oddDummy and evenDummy. Traverse the list and alternate appending nodes to oddTail and evenTail. Finally, connect oddTail.next = evenDummy.next and evenTail.next = null.

Algorithm

  1. Step 1: Create oddDummy = new ListNode(0), evenDummy = new ListNode(0).
  2. Step 2: oddTail = oddDummy, evenTail = evenDummy, isOdd = true, curr = head.
  3. Step 3: While curr != null:
  4. a. If isOdd: oddTail.next = curr, oddTail = oddTail.next.
  5. b. Else: evenTail.next = curr, evenTail = evenTail.next.
  6. c. isOdd = !isOdd, curr = curr.next.
  7. Step 4: evenTail.next = null, oddTail.next = evenDummy.next.
  8. Step 5: Return oddDummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* oddEvenList(ListNode* head) {
14 if (!head || !head->next) return head;
15
16 ListNode oddDummy(0), evenDummy(0);
17 ListNode* oddTail = &oddDummy;
18 ListNode* evenTail = &evenDummy;
19 ListNode* curr = head;
20 bool isOdd = true;
21
22 while (curr) {
23 ListNode* nextTemp = curr->next;
24 if (isOdd) {
25 oddTail->next = curr;
26 oddTail = oddTail->next;
27 } else {
28 evenTail->next = curr;
29 evenTail = evenTail->next;
30 }
31 isOdd = !isOdd;
32 curr = nextTemp;
33 }
34
35 evenTail->next = nullptr;
36 oddTail->next = evenDummy.next;
37 return oddDummy.next;
38 }
39};
40
41int main() {
42 ListNode* h = new ListNode(1);
43 h->next = new ListNode(2);
44 h->next->next = new ListNode(3);
45 h->next->next->next = new ListNode(4);
46 h->next->next->next->next = new ListNode(5);
47
48 Solution sol;
49 ListNode* res = sol.oddEvenList(h);
50
51 cout << "Better Parity Odd-Even: ";
52 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
53 cout << endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N) — Traverses the list in a single pass of N steps.
  • Space complexity: O(1) — Uses 2 static dummy sentinel nodes with O(1) pointers.

3. Optimal — In-Place Dual Pointer Unzipping

Intuition

Set odd = head, even = head.next, and evenHead = even. Loop while (even && even.next): set odd.next = even.next, advance odd = odd.next, set even.next = odd.next, advance even = even.next. When the loop finishes, weld odd.next = evenHead and return head.

Algorithm

  1. Step 1: If head == null || head.next == null, return head.
  2. Step 2: odd = head, even = head.next, evenHead = even.
  3. Step 3: While even != null && even.next != null:
  4. a. odd.next = even.next.
  5. b. odd = odd.next.
  6. c. even.next = odd.next.
  7. d. even = even.next.
  8. Step 4: odd.next = evenHead.
  9. Step 5: Return head.

Odd Even Linked List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Pair 1 begins unzipping
Visual state
Values and pointers at this exact step
linked list
odd → 1even → 2
Node 1
1
Node 2
2
Node 3
3
Node 4
4
Node 5
5
NULL
Check / comparison
even != null && even.next != null
Decision / next transition
Unzip pair
Why this step matters

Pair 1 begins unzipping.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* oddEvenList(ListNode* head) {
14 if (!head || !head->next) return head;
15
16 ListNode* odd = head;
17 ListNode* even = head->next;
18 ListNode* evenHead = even;
19
20 while (even && even->next) {
21 odd->next = even->next;
22 odd = odd->next;
23 even->next = odd->next;
24 even = even->next;
25 }
26
27 odd->next = evenHead;
28 return head;
29 }
30};
31
32int main() {
33 ListNode* h = new ListNode(1);
34 h->next = new ListNode(2);
35 h->next->next = new ListNode(3);
36 h->next->next->next = new ListNode(4);
37 h->next->next->next->next = new ListNode(5);
38
39 Solution sol;
40 ListNode* res = sol.oddEvenList(h);
41
42 cout << "Optimal Odd-Even: ";
43 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N) — Processes 2 nodes per loop iteration, executing in exactly N/2 steps. Strict O(N) linear time.
  • Space complexity: O(1) — Uses only three pointer variables (odd, even, evenHead) requiring strictly O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array Extraction & ReconstructionO(N)O(N)Traverse the linked list and collect odd-indexed nodes into one array and even-indexed nodes into another array. Reconstruct the list by creating new nodes or rewriting values.Auxiliary array allocation.
2.Better — Two Dummy Sentinel Lists with Parity ToggleO(N)O(1)Maintain two dummy heads oddDummy and evenDummy. Iterate through the list with a boolean flag isOdd = true, alternately appending nodes to either list, then merge.Unnecessary branching.
3.Optimal — In-Place Dual Pointer Unzipping (2 Pointers)OptimalO(N)O(1)Initialize odd = head, even = head.next, and evenHead = even. Loop while (even && even.next) updating odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next;. Finally set odd.next = evenHead.Optimal.

Common Pitfalls & Crucial Edge Cases

Confusing node values with node indices

The problem groups nodes by 1-based index (1st, 2nd, 3rd), not whether val % 2 == 0.

Looping on `odd && odd.next` instead of `even && even.next`

Since even is always ahead of odd, checking even and even.next guarantees that odd.next will never be null inside the loop.

Forgetting to save `evenHead`

Overwriting even without an anchor pointer loses the head of the even sublist.

Crucial Edge Cases to Validate:

  • Empty List — head = null -> returns null.
  • Single Node — head = [1] -> returns [1].
  • Two Nodes — head = [1, 2] -> returns [1, 2] unmodified.
  • Even Number of Nodes — head = [1, 2, 3, 4] -> loop ends with even == null, odd.next = evenHead -> [1, 3, 2, 4].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify immediately: 'Odd and Even refer to the node index positions (1st, 2nd, 3rd), not their integer values.'
  2. Explain the loop invariant: 'even is always ahead of odd, so looping while even && even.next naturally protects all pointer operations.'
  3. Highlight the final join step: odd.next = evenHead.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the loop condition while (even != null && even.next != null) sufficient and safe?

2.Does this algorithm preserve the relative stability of the odd and even groups?

3.What is the auxiliary space complexity of the optimal dual-pointer unzipping approach?

Back to DSA Sheet