Reorder Linked List by Parity
In many enterprise data processing systems, efficiently organizing sequential data based on certain attributes is crucial for performance and subsequent analysis. Consider a scenario where a stream of records, represented as a singly linked list, needs to be reordered. For instance, prioritizing records with even-numbered identifiers over odd-numbered ones, while maintaining their original relative sequence within their respective groups, can significantly optimize downstream processing steps or storage layouts.
This problem challenges you to implement a function that reorders a given singly linked list. The goal is to move all nodes with even integer values to appear before all nodes with odd integer values. The relative order of the even-valued nodes must remain unchanged, and similarly, the relative order of the odd-valued nodes must also be preserved.
Implement the reorderListByParity function which takes the head of a singly linked list and modifies it in-place (or constructs a new one by reusing existing nodes) according to the following rules:
Input:
head: A ListNode | null representing the head of a singly linked list. Each ListNode has an integer val and a next pointer to the subsequent node.
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
}
Output:
Return the ListNode | null representing the head of the reordered singly linked list.
head is null, the function should return null.ListNode objects; do not create new nodes for the values.Examples
Example 1
Input:
head = [1,2,3,4,5,6]
Output:
[2,4,6,1,3,5]
Note:
Even values 2, 4, 6 maintain their relative order and appear first. Odd values 1, 3, 5 maintain their relative order and appear after all even values.
Example 2
Input:
head = [7,1,3,5]
Output:
[7,1,3,5]
Note:
All values are odd. The list remains unchanged, preserving relative order.
Example 3
Input:
head = [2,8,4]
Output:
[2,8,4]
Note:
All values are even. The list remains unchanged, preserving relative order.
Example 4
Input:
head = [10,1,20,3,30,5]
Output:
[10,20,30,1,3,5]
Note:
Even nodes (10, 20, 30) appear first in their original order. Odd nodes (1, 3, 5) appear next in their original order.
Constraints
n is between 0 and 5000.1 <= Node.val <= 1000.Loading editor...