Reorder Linked List
At Groww, efficiently managing and displaying complex financial data is paramount. Imagine a scenario where a user's investment portfolio history is stored as a sequential list of transactions. To provide a unique, engaging overview, we want to reorder this history to highlight both the earliest and latest significant events alternately. This problem challenges you to implement an in-place reordering mechanism for a singly linked list, mimicking such a data presentation strategy.
You are given the head of a singly linked list. Your task is to reorder the list in-place such that if the original list is L0 → L1 → … → Ln-1 → Ln, it becomes L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ….
Specifically, you must:
Input:
head: The head node of a singly linked list. Each node has an integer val and a next pointer.
Output:
The function should not return anything. It should modify the list in-place. The head parameter will refer to the reordered list after the function call.
head is null, the function should do nothing.Examples
Example 1
Input:
head = [1,2,3,4]
Output:
[1,4,2,3]
Note:
The original list is 1 -> 2 -> 3 -> 4. Middle is between 2 and 3. First half: 1 -> 2 Second half: 3 -> 4 Reversed second half: 4 -> 3 Merging: 1 -> 4 -> 2 -> 3
Example 2
Input:
head = [1,2,3,4,5]
Output:
[1,5,2,4,3]
Note:
The original list is 1 -> 2 -> 3 -> 4 -> 5. Middle is 3. First half: 1 -> 2 -> 3 Second half: 4 -> 5 Reversed second half: 5 -> 4 Merging: 1 -> 5 -> 2 -> 4 -> 3
Example 3
Input:
head = [1,2]
Output:
[1,2]
Note:
The list has 2 nodes. No reordering is necessary.
Constraints
[0, 5 * 10^4].1 <= Node.val <= 1000.O(1) additional space complexity (excluding recursion stack space if using recursion, though an iterative approach is preferred for space efficiency).O(1) auxiliary space requirement.O(N) where N is the number of nodes.Loading editor...