Frontend School

Reorder Linked List into a Woven Pattern

DSA
hard

Reorder Linked List into a Woven Pattern

Hard
Linked List
Two Pointers
In-place

Overview

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.

What you need to do / Task

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:

  1. Find the middle of the linked list. If the list has an odd number of nodes, the first half should contain the extra middle node.
  2. Split the linked list into two distinct halves.
  3. Reverse the second half of the list in-place.
  4. Interleave the nodes from the first half and the reversed second half. The reordered list must start with a node from the original first half.

Input & output

  • Input: 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);
        }
    }
    
  • Output: The ListNode representing the head of the reordered linked list. The modification must be done in-place.

Clarifications

  • An empty list (head = null) or a list with a single node should remain unchanged.
  • The problem specifically requires in-place modification. You should not create new ListNode objects.

Examples

1

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.

2

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.

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.

4

Example 4

Input:

head = [1]

Output:

[1]

Note:

A single-node list remains unchanged as there's nothing to reorder.

Constraints

Constraints & assumptions

  • The number of nodes in the list N will be between 0 and 5 * 10^4.
  • 0 <= Node.val <= 1000.
  • The list is guaranteed to be a singly linked list.

Out of scope

  • Handling circular linked lists or doubly linked lists.
  • Creating a new linked list; the modification must be strictly in-place.

What interviewers evaluate

  • Algorithmic Correctness: Correctly identify and implement all sub-steps (finding middle, splitting, reversing, merging) with all edge cases handled.
  • Time and Space Complexity: Optimal solution achieving O(N) time and O(1) space complexity.
  • Code Structure and Readability: Clean, well-organized code with appropriate helper functions (if any) and meaningful variable names.

Loading editor...