How do you solve Odd Even Linked List?

Initialize two pointers: one for odd nodes starting at head, and one for even nodes starting at head.next. Keep a reference to the even head. Iterate while even and even.next exist, rewiring odd.next to even.next and moving odd forward, then rewiring even.next to odd.next and moving even forward. Finally, link the last odd node to the even head. Return the original head as the reordered list.

What pattern does Odd Even Linked List use?

The Pattern: Linked Lists (In-Place Reordering) The Heuristic: When reordering linked lists by position or grouping, maintain separate pointers for each group and rewire next pointers in a single pass to achieve O(1) space without losing track of sublist heads.

Odd Even Linked List | Linked Lists

Q: What is the time complexity of Odd Even Linked List?

O(n). The algorithm traverses the linked list once, performing constant-time pointer updates per node.

Problem

Given the head of a singly linked list, reorder the list so that all nodes at odd indices are grouped together followed by the nodes at even indices, preserving the relative order within each group, and return the reordered list's head.

The number of nodes in the linked list is in the range [0, 10⁴]
−10⁶ ≤ Node.val ≤ 10⁶

Example

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

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

Starting with the list 1->2->3->4->5, the algorithm separates nodes into odd and even indexed groups. The odd nodes are 1, 3, 5 and the even nodes are 2, 4. The algorithm links all odd nodes in order, then appends the even nodes. The final reordered list is 1->3->5->2->4.

Approach

Straightforward Solution

A naive approach would be to traverse the list, collect nodes into two separate arrays or lists (odd and even), then reconstruct the linked list by concatenating these arrays. This requires O(n) extra space and two passes.

Core Observation

The problem requires rearranging nodes based on their position indices, not their values. The key insight is that odd and even nodes form two separate linked lists that must be merged at the end.

Path to Optimal

Preview

The optimal approach uses two pointers to track the current odd and even nodes during a single traversal. By rewiring the next pointers in-place, the algorithm partitions the list into odd and even sublists without extra space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers: one for odd nodes starting at head, and one for even nodes starting at head.next…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm traverses the linked list once, performing constant-time pointer updates per node.

Space

O(1)

The solution uses only a fixed number of pointers regardless of input size, performing all operations in-place without additional data structures.

Solution

Python

1class Solution:
2    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
3        if not head or not head.next:
4            return head
5
6        odd = head
7        even = head.next
8        even_head = even
9
10        while even and even.next:
11            odd.next = even.next
12            odd = odd.next
13
14            even.next = odd.next
15            even = even.next
16
17        odd.next = even_head
18
19        return head

Step-by-Step Solution

1

Handle Base Cases with Empty or Single-Node Lists

3if not head or not head.next:
4    return head

Objective

To immediately return the input list if it is empty or contains only one node, as no reordering is needed.

Key Insight

Lists with zero or one node are already ordered by definition. Early returning avoids unnecessary processing and prevents null pointer exceptions in subsequent logic.

Interview Quick-Check

State & Boundaries

Check if head is None or head.next is None to handle trivial cases upfront.

Common Pitfalls & Bugs

Failing to handle empty or single-node lists can cause runtime errors or incorrect results.

2

Initialize Pointers to Track Odd and Even Sublists

To set up pointers for the current odd node, current even node, and the head of the even sublist for later concatenation.

3

Iteratively Rewire Next Pointers to Separate Odd and Even Nodes

To traverse the list, rewiring odd nodes to skip even nodes and even nodes to skip odd nodes, effectively partitioning the list into two linked lists.

4

Concatenate Odd and Even Sublists to Form the Final Reordered List

To link the last odd node to the head of the even sublist, completing the reordering.

5

Return the Head of the Reordered List

To return the head pointer of the reordered linked list as the function's result.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 11 Critical

odd.next = even.next

Rewire odd.next to skip the current even node and point to the next odd node.

This step partitions the list by linking odd nodes together, effectively removing even nodes from the odd sublist.

Line 14 Critical

even.next = odd.next

Rewire even.next to skip the current odd node and point to the next even node.

This step partitions the list by linking even nodes together, effectively removing odd nodes from the even sublist.

Line 3 Critical

if not head or not head.next:

Check if the list is empty or has only one node.

This early return handles trivial cases where no reordering is needed and prevents null pointer errors in subsequent logic.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why must the algorithm keep a separate reference to the head of the even nodes?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Odd Even Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Odd Even Linked List drill

or drill a free problem

1	`class Solution:`
2	`def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:`
3	`if not head or not head.next:`
4	`return head`
5
6	`odd = head`
7	`even = head.next`
8	`even_head = even`
9
10	`while even and even.next:`
11	`odd.next = even.next`
12	`odd = odd.next`
13
14	`even.next = odd.next`
15	`even = even.next`
16
17	`odd.next = even_head`
18
19	`return head`