Frontend School

Segregate and Alternately Merge Linked List

DSA
medium

Segregate and Alternately Merge Linked List

Medium
Linked List
Two Pointers
Manipulation

Overview

In healthcare data management, efficiently organizing and accessing patient records is crucial. Imagine a scenario where patient data, represented as nodes in a linked list, needs to be reorganized based on certain attributes for faster processing or specific reporting. This problem simulates a common data restructuring task where we categorize data points (nodes) based on a simple property (value parity) and then reassemble them in an interleaved manner to facilitate sequential access for different analytical workflows.

What you need to do / Task

You are given the head of a singly linked list. Your task is to reorganize this list according to the following rules:

  1. Segregate Nodes: Separate the nodes into two distinct sub-lists: one containing all nodes with even integer values, and another containing all nodes with odd integer values. The relative order of nodes within their respective parity groups must be preserved from the original list.
  2. Alternately Merge: Merge these two segregated sub-lists back into a single list. The merged list should alternate nodes between the even and odd sub-lists.
    • The merged list must always start with an even node, if an even node is available.
    • If one sub-list runs out of nodes, append the remaining nodes of the other sub-list to the merged list.

You should perform this operation by modifying the next pointers of the existing nodes; do not create new nodes.

Input & output

Input:

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

Output:

  • A ListNode | null representing the head of the reorganized linked list.

Clarifications

  • Empty list: If the input head is null, return null.
  • Single node list: If the list contains only one node, return the head as is.
  • All even or all odd: If all nodes have even values, or all nodes have odd values, the segregation step will result in one empty sub-list. The merging step should then simply return the non-empty sub-list.
  • Node values: Node values (val) will be non-negative integers.

Examples

1

Example 1

Input:

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

Output:

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

Note:

Original list: 1 -> 2 -> 3 -> 4 -> 5 -> 6. Even nodes (preserving relative order): 2 -> 4 -> 6. Odd nodes (preserving relative order): 1 -> 3 -> 5. Merged (starting with even, alternating): 2 -> 1 -> 4 -> 3 -> 6 -> 5.

2

Example 2

Input:

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

Output:

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

Note:

Original list: 2 -> 4 -> 6 -> 1 -> 3 -> 5. Even nodes: 2 -> 4 -> 6. Odd nodes: 1 -> 3 -> 5. Merged: 2 -> 1 -> 4 -> 3 -> 6 -> 5 (demonstrates stable sorting and merge).

3

Example 3

Input:

head = [1,3,5]

Output:

[1,3,5]

Note:

Original list: 1 -> 3 -> 5. Even nodes: (empty list). Odd nodes: 1 -> 3 -> 5. Merged: 1 -> 3 -> 5 (Starts with odd because no even nodes are available).

4

Example 4

Input:

head = [2,4,6]

Output:

[2,4,6]

Note:

Original list: 2 -> 4 -> 6. Even nodes: 2 -> 4 -> 6. Odd nodes: (empty list). Merged: 2 -> 4 -> 6.

5

Example 5

Input:

head = []

Output:

[]

Note:

Empty list input results in an empty list output.

6

Example 6

Input:

head = [7]

Output:

[7]

Note:

Single node list input results in the same list output.

Constraints

Constraints & assumptions

  • The number of nodes in the list will be in the range [0, 5000].
  • 0 <= Node.val <= 10^9.
  • The problem uses a singly linked list structure.
  • Memory usage should be O(1) auxiliary space (excluding input/output list structure).
  • Time complexity should be O(N), where N is the number of nodes in the list.

Out of scope

  • Handling circular linked lists.
  • Validation of ListNode structure (assume valid val and next pointers).
  • Error handling for non-integer Node.val or other invalid data types.

What interviewers evaluate

  • Correctness: The solution correctly segregates and merges nodes according to all specified rules, handling edge cases.
  • Efficiency: The solution achieves the optimal time and space complexity (O(N) time, O(1) auxiliary space).
  • Code Structure & Readability: The code is well-organized, easy to understand, and follows good programming practices.
  • Linked List Manipulation: Demonstrates strong understanding of pointer manipulation in linked lists.

Loading editor...