Frontend School

Reorder Linked List

DSA
hard

Reorder Linked List

Hard
Linked List
Two Pointers
In-place

Overview

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.

What you need to do / Task

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:

  1. Find the middle of the linked list.
  2. Split the list into two halves.
  3. Reverse the second half of the list.
  4. Merge the first half and the reversed second half alternately.
  5. Perform this operation in-place without modifying the values of the nodes. Only the nodes themselves can be changed.

Input & output

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.

Clarifications

  • Empty List: If the input head is null, the function should do nothing.
  • List with 1 or 2 nodes: For lists with 1 or 2 nodes, no reordering is necessary. The function should handle these cases gracefully, effectively doing nothing.
  • Even/Odd Length: The logic should correctly handle lists of both even and odd lengths.

Examples

1

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

2

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

3

Example 3

Input:

head = [1,2]

Output:

[1,2]

Note:

The list has 2 nodes. No reordering is necessary.

Constraints

Constraints & assumptions

  • The number of nodes in the list will be in the range [0, 5 * 10^4].
  • 1 <= Node.val <= 1000.
  • The problem requires an in-place solution. You are not allowed to create new nodes.
  • You must solve this problem with O(1) additional space complexity (excluding recursion stack space if using recursion, though an iterative approach is preferred for space efficiency).

What interviewers evaluate

  • Correctness and Edge Cases: The solution should correctly reorder the list for all valid inputs, including edge cases like empty lists, single-node lists, and two-node lists.
  • Algorithm Design: Demonstrates a clear understanding of linked list manipulation, including finding the middle, reversing, and merging.
  • Space Complexity: Achieves the O(1) auxiliary space requirement.
  • Time Complexity: Optimizes for the best possible time complexity, typically O(N) where N is the number of nodes.

Loading editor...