Reorder Linked List into a Woven Pattern
Lenskart's supply chain often deals with sequences of tasks or product components that need to be processed in a specific, often interleaved, order for optimal efficiency or quality control. Imagine a scenario where components from two different sub-assemblies need to be integrated alternately on a production line. This problem simulates reordering a linear sequence of items (represented by a linked list) into such a "woven" pattern, crucial for optimizing workflows and minimizing bottlenecks in our manufacturing or fulfillment processes.
Given the head of a singly linked list, reorder it in-place such that the first half of the list and the reversed second half are interleaved. The reordering must be performed by modifying the next pointers of the existing nodes, without creating new nodes.
Specifically, your solution should:
head: A ListNode representing the head of the singly linked list. Each ListNode has an integer val and a next pointer.
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
}
ListNode representing the head of the reordered linked list. The modification must be done in-place.head = null) or a list with a single node should remain unchanged.ListNode objects.Examples
Example 1
Input:
head = [1,2,3,4,5,6]
Output:
[1,6,2,5,3,4]
Note:
Original list: 1->2->3->4->5->6. First half: 1->2->3. Second half: 4->5->6. Reversed second half: 6->5->4. Interleaving: 1->6->2->5->3->4.
Example 2
Input:
head = [1,2,3,4,5]
Output:
[1,5,2,4,3]
Note:
Original list: 1->2->3->4->5. First half: 1->2->3. Second half: 4->5. Reversed second half: 5->4. Interleaving: 1->5->2->4->3.
Example 3
Input:
head = [1,2]
Output:
[1,2]
Note:
Original list: 1->2. First half: 1. Second half: 2. Reversed second half: 2. Interleaving: 1->2. No visible change for a list of two nodes, but the logic should still correctly process it.
Example 4
Input:
head = [1]
Output:
[1]
Note:
A single-node list remains unchanged as there's nothing to reorder.
Constraints
N will be between 0 and 5 * 10^4.0 <= Node.val <= 1000.Loading editor...