Rearrange Linked List by Parity
In healthcare data systems, linked lists are sometimes used to represent sequences of records, such as patient visits or medication events. For certain analytical tasks, it can be beneficial to reorder these sequences based on specific criteria to optimize processing or improve data locality. This problem challenges you to efficiently rearrange a linked list by separating nodes based on their original index parity.
You are given the head of a singly linked list. Your task is to rearrange the list such that all nodes at odd indices appear before all nodes at even indices. The relative order of nodes within the odd group and within the even group must be preserved. The first node is considered to be at index 0 (an odd index for the purpose of this problem, as it's the 1st node).
For example:
If the input list is 1 -> 2 -> 3 -> 4 -> 5
1, 3, 52, 4
The rearranged list should be 1 -> 3 -> 5 -> 2 -> 4.head: A ListNode representing the head of a singly linked list.ListNode representing the head of the rearranged linked list.Examples
Example 1
Input:
head = [1,2,3,4,5]
Output:
[1,3,5,2,4]
Note:
Original list: 1 (idx 0) -> 2 (idx 1) -> 3 (idx 2) -> 4 (idx 3) -> 5 (idx 4). Odd-indexed nodes: 1, 3, 5. Even-indexed nodes: 2, 4. Rearranged: 1 -> 3 -> 5 -> 2 -> 4.
Example 2
Input:
head = [2,1,3,5,6,4,7]
Output:
[2,3,6,7,1,5,4]
Note:
Original list: 2 (idx 0) -> 1 (idx 1) -> 3 (idx 2) -> 5 (idx 3) -> 6 (idx 4) -> 4 (idx 5) -> 7 (idx 6). Odd-indexed nodes: 2, 3, 6, 7. Even-indexed nodes: 1, 5, 4. Rearranged: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4.
Example 3
Input:
head = [1,2,3]
Output:
[1,3,2]
Note:
Original list: 1 (idx 0) -> 2 (idx 1) -> 3 (idx 2). Odd-indexed nodes: 1, 3. Even-indexed nodes: 2. Rearranged: 1 -> 3 -> 2.
Constraints
[0, 10^4].[-10^6, 10^6].Loading editor...