328. Odd Even Linked List

How to solve Odd Even Linked List (LeetCode 328): the approach in brief

The problem

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.

Pattern

Odd Even Linked List is a Linked List Manipulation Patterns problem, in the Reordering / Partitioning subpattern. The pattern covers in-place reversal, merging sorted lists, reordering, and intersection detection

Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.

Approach outline

1. Consider how you can traverse the linked list while rearranging nodes in place without using extra memory.
2. Think about maintaining two separate pointers: one for nodes at odd positions and another for even positions as you iterate through the list.
3. How can you link the odd-indexed nodes together and the even-indexed nodes together during a single pass through the list?

Complexity

The reference solution runs in O(n) time and O(1) space.

Asked at

Odd Even Linked List has been reported in interviews at Bloomberg, Oracle, Facebook, Google.