Reorder Linked List
In Livspace, optimizing data presentation for dynamic content is crucial. Imagine a scenario where product recommendations or design inspirations are displayed in a unique, interleaved pattern to maximize user engagement. For instance, instead of a linear display Item A, Item B, Item C, Item D, we might want Item A, Item D, Item B, Item C to create a more compelling visual flow. This problem challenges you to implement an algorithm that reorders a singly linked list in-place to achieve such a specific interleaved pattern.
Given the head of a singly linked list, reorder it such that:
L0 → L1 → … → Ln-1 → Ln
becomes:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You must do this in-place without modifying the values in the list's nodes. Only the nodes themselves may be changed.
head: A ListNode object representing the head of the singly linked list. The list is guaranteed to be valid.void. The function should modify the given linked list in-place. No explicit return value is expected.head is null, though constraints guarantee n >= 1) or contains only one node, no reordering is needed. The function should handle these cases gracefully.n will be between 1 and 50,000. Node values will be between 1 and 1000.Examples
Example 1
Input:
head = [1,2,3,4]
Output:
[1,4,2,3]
Note:
The original list is 1 -> 2 -> 3 -> 4. After reordering, it becomes 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. After reordering, it becomes 1 -> 5 -> 2 -> 4 -> 3.
Example 3
Input:
head = [1]
Output:
[1]
Note:
A list with a single node requires no reordering.
Constraints
n) is between 1 and 50,000.1 <= Node.val <= 1000head being null if n is specified as 1 <= n. The problem statement guarantees a valid head for n >= 1.n beyond the typical O(N) linear scan, which is the expected approach for this problem.Loading editor...