Segregate even and odd nodes in a linked list
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]
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;}