Frontend School

Reorder Linked List by Parity

DSA
medium

Reorder Linked List by Parity

Medium
Linked List
Two Pointers
Partition

Overview

In many enterprise data processing systems, efficiently organizing sequential data based on certain attributes is crucial for performance and subsequent analysis. Consider a scenario where a stream of records, represented as a singly linked list, needs to be reordered. For instance, prioritizing records with even-numbered identifiers over odd-numbered ones, while maintaining their original relative sequence within their respective groups, can significantly optimize downstream processing steps or storage layouts.

This problem challenges you to implement a function that reorders a given singly linked list. The goal is to move all nodes with even integer values to appear before all nodes with odd integer values. The relative order of the even-valued nodes must remain unchanged, and similarly, the relative order of the odd-valued nodes must also be preserved.

What you need to do / Task

Implement the reorderListByParity function which takes the head of a singly linked list and modifies it in-place (or constructs a new one by reusing existing nodes) according to the following rules:

  1. All nodes containing an even integer value must appear before all nodes containing an odd integer value.
  2. The relative order of the even-valued nodes must be preserved from the original list.
  3. The relative order of the odd-valued nodes must be preserved from the original list.

Input & output

Input: head: A ListNode | null representing the head of a singly linked list. Each ListNode has an integer val and a next pointer to the subsequent node.

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: Return the ListNode | null representing the head of the reordered singly linked list.

Clarifications

  • Empty list: If the input head is null, the function should return null.
  • Single node list: If the list contains only one node, its parity doesn't matter for reordering; the list should remain unchanged.
  • All even/all odd: If all nodes have even values or all have odd values, the list's relative order should still be preserved, effectively meaning no change in sequence.
  • Node reuse: You should reuse the existing ListNode objects; do not create new nodes for the values.

Examples

1

Example 1

Input:

head = [1,2,3,4,5,6]

Output:

[2,4,6,1,3,5]

Note:

Even values 2, 4, 6 maintain their relative order and appear first. Odd values 1, 3, 5 maintain their relative order and appear after all even values.

2

Example 2

Input:

head = [7,1,3,5]

Output:

[7,1,3,5]

Note:

All values are odd. The list remains unchanged, preserving relative order.

3

Example 3

Input:

head = [2,8,4]

Output:

[2,8,4]

Note:

All values are even. The list remains unchanged, preserving relative order.

4

Example 4

Input:

head = [10,1,20,3,30,5]

Output:

[10,20,30,1,3,5]

Note:

Even nodes (10, 20, 30) appear first in their original order. Odd nodes (1, 3, 5) appear next in their original order.

Constraints

Constraints & assumptions

  • The number of nodes in the list n is between 0 and 5000.
  • 1 <= Node.val <= 1000.
  • The given list is a valid singly linked list.

Out of scope

  • Handling circular linked lists.
  • Validating the input linked list structure (assume it's well-formed).
  • Optimizing for extreme memory constraints that would disallow auxiliary pointers (standard O(1) auxiliary space for pointers is acceptable).

What interviewers evaluate

  • Correctness: The reordered list strictly adheres to the parity and relative order preservation rules.
  • Efficiency: The solution operates within optimal time (O(N)) and space (O(1) auxiliary) complexity.
  • Edge Case Handling: Correctly manages empty lists, single-node lists, and lists with uniform parity values.
  • Code Quality: Demonstrates clean, readable, and well-structured code with appropriate variable naming.

Loading editor...