Interleave Linked List Halves
In many data processing scenarios, especially those involving sequential data or queues, there's a need to rearrange elements to optimize access patterns or for specific display requirements. This problem challenges you to efficiently interleave the nodes of a singly linked list, combining its first and second halves in an alternating fashion. Mastery of in-place linked list manipulations is crucial for building high-performance systems.
Given the head of a singly linked list, rearrange it such that nodes from the first half and the second half are interleaved. The rearrangement must be performed in-place, modifying the original list structure. You should return the head of the modified list.
Specifically, your task involves the following steps:
Input:
head: ListNode | null - The head of a singly linked list. Each ListNode has an integer val and a next pointer to the next node.Output:
ListNode | null - The head of the rearranged linked list.head is null, return null.head.Examples
Example 1
Input:
head = [1,2,3,4,5,6]
Output:
[1,6,2,5,3,4]
Note:
The list is split into [1,2,3] and [4,5,6]. The second half is reversed to [6,5,4]. Then, they are interleaved: 1 from first, 6 from second, 2 from first, 5 from second, 3 from first, and 4 from second.
Example 2
Input:
head = [1,2,3,4,5]
Output:
[1,5,2,4,3]
Note:
The list is split into [1,2,3] (first half with middle node) and [4,5]. The second half is reversed to [5,4]. Then, they are interleaved: 1 from first, 5 from second, 2 from first, 4 from second, and finally 3 from the remaining first half.
Example 3
Input:
head = [1,2]
Output:
[1,2]
Note:
For a two-node list, the first half is [1] and the second is [2]. Reversing the second half gives [2]. Interleaving yields [1,2], which is effectively no change but demonstrates the logic for small lists.
Constraints
0 <= Number of nodes <= 5 * 10^41 <= Node.val <= 1000O(N), where N is the number of nodes in the list.O(1).Node.val values.null check.Loading editor...