Odd Even Linked List

The key idea

Weave two sub-lists in a single pass without extra space: an odd chain and an even chain. Walk both pointers forward by relinking odd.next = even.next and even.next = odd.next. When the even chain ends, splice the saved even head onto the tail of the odd chain.

Problem

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

The first node is considered odd, the second node even, and so on. Note that the relative order of nodes inside both the odd group and the even group must stay the same as in the input.

Solve it in O(1) extra space and O(n) time.

Constraints

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

Examples

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

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

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →