Move Even Values Before Odd Values
You are given head, the first node of a singly linked list of integers.
Rearrange the list so that every node with an even value comes first, followed by every node with an odd value. Inside each group, keep the nodes in the same order they had in the original list. Return the head of the rearranged list.
A value is even when it divides by 2 with no remainder. So 0, -4 and 12 are even, and -3 and 7 are odd.
How the input is shown
A list is shown as an array of its values from head to tail. For example, [7, 4, 3] is the list 7 -> 4 -> 3, and [] is an empty list (head is null). Your function returns a list in the same way.
Note
- Move the nodes; you do not need to create new ones.
- Hint: walk the list once and build two separate chains, one for even nodes and one for odd nodes. Keep a pointer to the last node of each chain. At the end, join the end of the even chain to the start of the odd chain, and make sure the last node points to
null. This takes O(n) time and O(1) extra space.
Examples
Example 1
- Input:
- [7,4,3,10,6,1]
- Output:
- [4,10,6,7,3,1]
The even values are 4, 10 and 6, in that order. The odd values are 7, 3 and 1, in that order. The even group comes first.
Example 2
- Input:
- [0,-3,-4,9]
- Output:
- [0,-4,-3,9]
0 and -4 are even, so they come first. -3 and 9 are odd, so they follow. Each group keeps its original order.
Example 3
- Input:
- [5,9,1]
- Output:
- [5,9,1]
There are no even values, so the list does not change.
Constraints
0 <=number of nodes<= 60-100 <= Node.val <= 100
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.