Frontend School

Rearrange Product Bundles by Parity

DSA
medium

Rearrange Product Bundles by Parity

Medium
Linked List
Two Pointers
Partition

Overview

At Nykaa, efficient processing of product bundles is crucial for inventory management and order fulfillment. Sometimes, bundles need to be processed in a specific order based on their unique identifiers. This problem simulates a scenario where product bundles, identified by numerical IDs, need to be re-sorted to prioritize bundles with even IDs over those with odd IDs, while maintaining their original relative sequence within their respective parity groups.

What you need to do / Task

You are given the head of a singly linked list, where each node contains a unique positive integer representing a product bundle ID. Your task is to rearrange the linked list such that:

  1. All nodes with an even bundle ID appear before all nodes with an odd bundle ID.
  2. The relative order of nodes within the even-ID group must remain the same as in the original list.
  3. The relative order of nodes within the odd-ID group must remain the same as in the original list.

You should return the head of the rearranged linked list.

Input & output

  • Input:
    • head: The head of a singly linked list. Each ListNode contains a positive integer val representing a product bundle ID.
  • Output:
    • The head of the rearranged singly linked list, satisfying the conditions described above.

Clarifications

  • The linked list can be empty (head is null).
  • The linked list can contain a single node.
  • All bundle IDs (val) are positive integers.
  • You should modify the existing nodes' next pointers; do not create new nodes for the values.

Examples

1

Example 1

Input:

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

Output:

[2,4,1,3,5]

Note:

Even IDs (2, 4) maintain relative order and come first. Odd IDs (1, 3, 5) maintain relative order and come after.

2

Example 2

Input:

head = [2,4,6]

Output:

[2,4,6]

Note:

All IDs are even, so their relative order is preserved and no rearrangement is needed.

3

Example 3

Input:

head = [1,3,5]

Output:

[1,3,5]

Note:

All IDs are odd, so their relative order is preserved and no rearrangement is needed.

4

Example 4

Input:

head = []

Output:

[]

Note:

An empty list remains empty.

Constraints

Constraints & assumptions

  • The number of nodes in the list is between 0 and 10^4.
  • Each node's val (bundle ID) is an integer between 1 and 10^9.

What interviewers evaluate

  • Correctness: The solution correctly rearranges the linked list according to all specified conditions, handling edge cases gracefully.
  • Time Complexity: The solution processes the linked list efficiently, ideally in a single pass (O(N)).
  • Space Complexity: The solution uses minimal auxiliary space, ideally O(1).
  • Code Structure & Readability: The code is well-organized, easy to understand, and follows good coding practices.

Loading editor...