Segregate even and odd nodes in a linked list

Easy

Problem

Rearrange the list so that all even-valued nodes come before all odd-valued nodes, keeping the original relative order within each group.

Example 1

Input:  17 → 15 → 8 → 12 → 10 → 5 → 4
Output: 8 → 12 → 10 → 4 → 17 → 15 → 5

Also asked as: Segregate even and odd nodes in a Linked List

Test cases

Case 1

Input:    [17,15,8,12,10,5,4]
Expected: [8,12,10,4,17,15,5]

Case 2

Input:    [1,2]
Expected: [2,1]

Case 3

Input:    [1,3,5]
Expected: [1,3,5]

Case 4

Input:    [2,4]
Expected: [2,4]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two chains, then join

Time O(n)Space O(1)

Build an even-value chain and an odd-value chain in one pass; append odd after even.

function segregateEvenOdd(head) {
const evenD = { next: null }, oddD = { next: null };
let e = evenD, o = oddD;
for (let n = head; n; n = n.next) {
if (n.val % 2 === 0) { e.next = n; e = n; } else { o.next = n; o = n; }
}
e.next = oddD.next;
o.next = null;
return evenD.next;
}