Segregate and Alternately Merge Linked List
In healthcare data management, efficiently organizing and accessing patient records is crucial. Imagine a scenario where patient data, represented as nodes in a linked list, needs to be reorganized based on certain attributes for faster processing or specific reporting. This problem simulates a common data restructuring task where we categorize data points (nodes) based on a simple property (value parity) and then reassemble them in an interleaved manner to facilitate sequential access for different analytical workflows.
You are given the head of a singly linked list. Your task is to reorganize this list according to the following rules:
You should perform this operation by modifying the next pointers of the existing nodes; do not create new nodes.
Input:
head: A ListNode | null representing the head of the singly linked list. Each ListNode has an integer val and a next pointer to the subsequent node.Output:
ListNode | null representing the head of the reorganized linked list.head is null, return null.val) will be non-negative integers.Examples
Example 1
Input:
head = [1,2,3,4,5,6]
Output:
[2,1,4,3,6,5]
Note:
Original list: 1 -> 2 -> 3 -> 4 -> 5 -> 6. Even nodes (preserving relative order): 2 -> 4 -> 6. Odd nodes (preserving relative order): 1 -> 3 -> 5. Merged (starting with even, alternating): 2 -> 1 -> 4 -> 3 -> 6 -> 5.
Example 2
Input:
head = [2,4,6,1,3,5]
Output:
[2,1,4,3,6,5]
Note:
Original list: 2 -> 4 -> 6 -> 1 -> 3 -> 5. Even nodes: 2 -> 4 -> 6. Odd nodes: 1 -> 3 -> 5. Merged: 2 -> 1 -> 4 -> 3 -> 6 -> 5 (demonstrates stable sorting and merge).
Example 3
Input:
head = [1,3,5]
Output:
[1,3,5]
Note:
Original list: 1 -> 3 -> 5. Even nodes: (empty list). Odd nodes: 1 -> 3 -> 5. Merged: 1 -> 3 -> 5 (Starts with odd because no even nodes are available).
Example 4
Input:
head = [2,4,6]
Output:
[2,4,6]
Note:
Original list: 2 -> 4 -> 6. Even nodes: 2 -> 4 -> 6. Odd nodes: (empty list). Merged: 2 -> 4 -> 6.
Example 5
Input:
head = []
Output:
[]
Note:
Empty list input results in an empty list output.
Example 6
Input:
head = [7]
Output:
[7]
Note:
Single node list input results in the same list output.
Constraints
[0, 5000].0 <= Node.val <= 10^9.ListNode structure (assume valid val and next pointers).Node.val or other invalid data types.Loading editor...