322. Segregate Even and Odd Nodes

Given the head of a singly linked list containing integers, rearrange it so all even-valued nodes come before all odd-valued nodes. Preserve the relative order within each group. Return the head.

Note: 'even/odd' refers to node values, not positions.

Input: Head of a singly linked list.

Output: Head of the rearranged list (evens first, then odds).

Examples

Input: [1,2,3,4,5]
Output: [2,4,1,3,5]
Explanation: Evens: [2,4]. Odds: [1,3,5]. Merge: [2,4,1,3,5].

Input: [2,1,3,5,6,4,1,2,3]
Output: [2,6,4,2,1,3,5,1,3]
Explanation: Evens in order: [2,6,4,2]. Odds in order: [1,3,5,1,3]. Concatenate.

Input: [1,3,5]
Output: [1,3,5]
Explanation: No even nodes. Result unchanged.

Constraints

• 1<=nodes<=10^4
• -10^9<=Node.val<=10^9

Asked by