Frontend School

Group Even and Odd Nodes in Linked List

DSA
medium

Group Even and Odd Nodes in Linked List

Medium
Linked List
Two Pointers
Partition

Overview

In data processing pipelines, it's often necessary to reorder or partition data streams based on certain criteria to optimize subsequent operations. For instance, grouping records by type or priority can improve cache locality or parallel processing efficiency. This problem challenges you to efficiently reorder a singly linked list, separating its nodes based on the parity (even or odd) of their values.

What you need to do / Task

You are given the head of a singly linked list. Your task is to rearrange the nodes in the list such that all nodes with even integer values appear before all nodes with odd integer values. It is crucial that the relative order of the even-valued nodes among themselves, and the relative order of the odd-valued nodes among themselves, must be preserved from the original list.

Return the head of the reordered linked list.

Input & output

Input:

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

Output:

  • ListNode | null: The head of the reordered linked list, where all even-valued nodes precede all odd-valued nodes, and the relative order within each group is maintained. If the input list is empty, return null.

Clarifications

  • Empty List: If the input head is null, the function should return null.
  • Single Node List: If the list contains only one node, return that node as is.
  • Node Values: Node values are non-negative integers. Parity (even/odd) is determined by val % 2 == 0 for even, and val % 2 != 0 for odd.
  • Original List Modification: You should modify the existing list by re-pointing the next pointers of the nodes. You should not create new nodes for the solution.

Examples

1

Example 1

Input:

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

Output:

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

Note:

Even nodes (2,4,6) maintain their relative order. Odd nodes (1,3,5) maintain their relative order. All even nodes come before all odd nodes.

2

Example 2

Input:

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

Output:

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

Note:

Even nodes (2,4,6) maintain their relative order. Odd nodes (1,3,5) maintain their relative order. All even nodes come before all odd nodes.

3

Example 3

Input:

head = [1,3,5]

Output:

[1,3,5]

Note:

All nodes are odd. Their relative order is preserved.

4

Example 4

Input:

head = [2,4,6]

Output:

[2,4,6]

Note:

All nodes are even. Their relative order is preserved.

5

Example 5

Input:

head = []

Output:

[]

Note:

An empty list should return an empty list.

Constraints

Constraints & assumptions

  • The number of nodes in the list is in the range [0, 10^4].
  • 0 <= Node.val <= 10^9.
  • The list is singly linked.

Out of scope

  • Handling circular linked lists.
  • Sorting the values within the even or odd groups (only relative order preservation is required).

What interviewers evaluate

  • Correctness: Does the solution correctly partition the list and preserve relative order within groups?
  • Efficiency: Is the solution optimal in terms of time and space complexity (O(N) time, O(1) space)?
  • Edge Cases: Does the solution gracefully handle empty lists, single-node lists, or lists containing only even/odd numbers?
  • Code Quality: Is the code clean, readable, and well-structured, demonstrating good software engineering practices?

Loading editor...