Frontend School

Reorder Linked List

DSA
medium

Reorder Linked List

Medium
Linked List
Two Pointers

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: head: A ListNode object representing the head of the singly linked list. The list is guaranteed to be valid.
  • Output: void. The function should modify the given linked list in-place. No explicit return value is expected.

Clarifications

  • Empty list or single node list: If the list is empty (head is null, though constraints guarantee n >= 1) or contains only one node, no reordering is needed. The function should handle these cases gracefully.
  • Even/Odd number of nodes: The reordering logic should correctly handle lists with both an even and an odd number of nodes.
  • Constraints: The number of nodes n will be between 1 and 50,000. Node values will be between 1 and 1000.

Examples

1

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.

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. After reordering, it becomes 1 -> 5 -> 2 -> 4 -> 3.

3

Example 3

Input:

head = [1]

Output:

[1]

Note:

A list with a single node requires no reordering.

Constraints

Constraints & assumptions

  • The number of nodes in the list (n) is between 1 and 50,000.
  • 1 <= Node.val <= 1000
  • The problem requires an in-place modification of the linked list. You are not allowed to create new nodes.

Out of scope

  • Handling invalid input like head being null if n is specified as 1 <= n. The problem statement guarantees a valid head for n >= 1.
  • Optimizing for extremely large n beyond the typical O(N) linear scan, which is the expected approach for this problem.

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly reorder the linked list for all valid inputs, including edge cases?
  • Time Complexity: Is the solution efficient, ideally achieving O(N) time complexity where N is the number of nodes?
  • Space Complexity: Does the solution operate in-place, achieving O(1) auxiliary space complexity?
  • Code Structure & Readability: Is the code well-organized, easy to understand, and does it follow good programming practices?
  • Problem Decomposition: Does the candidate break down the problem into logical sub-problems (e.g., finding middle, reversing, merging)?

Loading editor...