Frontend School

Reorder Linked List

DSA
medium

Reorder Linked List

Medium
Linked List
Two Pointers
In-place

Overview

Imagine you're building a feature for a music playlist application where users can "shuffle" a playlist in a specific, aesthetically pleasing pattern. Instead of a random shuffle, the design calls for an "interleaved" reordering: the first song, then the last, then the second, then the second-to-last, and so on. This ensures a blend of old and new tracks throughout the listening experience. Your task is to implement this reordering for a given playlist represented as a singly linked list.

What you need to do / Task

Given the head of a singly linked list L: L0 → L1 → … → Ln-1 → Ln, reorder it to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …. You must do this in-place without modifying the nodes' values.

Input & output

  • Input: head: A ListNode representing the head of the singly linked list.
  • Output: The function should reorder the list in-place. It does not need to return anything explicitly (void). The modified list should be accessible via the original head reference.

Clarifications

  • Empty list: If head is null, the function should do nothing.
  • Short list: If the list has 1 or 2 nodes, no reordering is needed (or the reordering naturally results in the same list).

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: 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: 1 -> 5 -> 2 -> 4 -> 3.

3

Example 3

Input:

head = [1,2]

Output:

[1,2]

Note:

A list with 2 nodes is already in the desired order, or too short for effective reordering. The list remains 1 -> 2.

Constraints

Constraints & assumptions

  • The number of nodes n in the list is between 0 and 5 * 10^4.
  • Node values are integers.
  • The reordering must be done in-place. You are not allowed to create new nodes.
  • You may not modify the values in the list's nodes. Only the pointers can be changed.

Out of scope

  • Handling circular linked lists.
  • Memory optimization beyond typical linked list operations (e.g., not expected to reduce memory complexity below O(1) if a stack/array is naturally used for a sub-step, though O(1) space is achievable for this problem).

What interviewers evaluate

  • Problem Decomposition: Ability to break down the problem into sub-problems (e.g., finding middle, reversing a sub-list, merging).
  • Correctness: The reordered list matches the specification for various edge cases (empty, short, even/odd length).
  • Efficiency: Solution achieves optimal time and space complexity (O(N) time, O(1) space).
  • Code Quality: Readability, clarity, and proper handling of pointers.

Loading editor...