Frontend School

Compact and Segment Reverse Linked List

DSA
hard

Compact and Segment Reverse Linked List

Hard
Linked List
Two Pointers
Reversal

Overview

At MakeMyTrip, efficient data processing is crucial for managing vast amounts of booking information. Imagine a scenario where a linked list represents a sequence of booking events. Some events are "confirmed" (valid) while others are "pending" or "cancelled" (invalid). To optimize our processing workflows, we need to first prioritize and group confirmed events, followed by pending/cancelled ones. Furthermore, for quick review, the most recent few confirmed and pending events need to be easily accessible, which can be achieved by reversing their order.

What you need to do / Task

You are given the head of a singly linked list and an integer K. Each node in the list has an integer value. A node is considered valid if its value is strictly positive (value > 0). All other nodes (where value <= 0) are considered invalid. Your task is to implement a function that performs two distinct operations on the given linked list, in the specified order:

  1. Compaction: Reorder the list such that all valid nodes appear first, followed by all invalid nodes.
    • The relative order of valid nodes among themselves must be preserved.
    • The relative order of invalid nodes among themselves must also be preserved.
  2. Segment Reverse: After the compaction, reverse the first K nodes in the valid segment. Then, reverse the first K nodes in the invalid segment.
    • If the valid segment has fewer than K nodes, reverse all of them.
    • If the invalid segment has fewer than K nodes, reverse all of them.
    • The connection between the valid and invalid segments must be maintained.

Your function should return the head of the reordered and modified linked list.

Input & output

Function Signature:

function compactAndSegmentReverse(head: ListNode | null, K: number): ListNode | null

Input:

  • head: A ListNode object representing the head of the singly linked list. Each ListNode has an integer value and a next pointer. Can be null for an empty list.
  • K: An integer representing the number of nodes to reverse in each segment.

Output:

  • A ListNode object representing the head of the modified linked list after compaction and segment reversal. Returns null if the input list was empty.

Clarifications

  • An empty input list (head = null) should result in null output.
  • If K is larger than the number of nodes in a segment, you should reverse all nodes present in that segment.

Examples

1

Example 1

Input:

head = [1, -2, 3, 4, -5, 6, 0, 7], K = 2

Output:

[3,1,4,6,7,-5,-2,0]

Note:

  1. Compaction: Valid nodes (1, 3, 4, 6, 7) and Invalid nodes (-2, -5, 0). Compacted list: 1 -> 3 -> 4 -> 6 -> 7 -> -2 -> -5 -> 0
  2. Segment Reverse (K=2):
    • Reverse first 2 valid nodes (1 -> 3 becomes 3 -> 1): 3 -> 1 -> 4 -> 6 -> 7 -> -2 -> -5 -> 0
    • Reverse first 2 invalid nodes (-2 -> -5 becomes -5 -> -2): 3 -> 1 -> 4 -> 6 -> 7 -> -5 -> -2 -> 0
2

Example 2

Input:

head = [10, 20, 30], K = 5

Output:

[30,20,10]

Note:

  1. Compaction: All nodes are valid. List remains 10 -> 20 -> 30.
  2. Segment Reverse (K=5): Valid segment has 3 nodes. Since K (5) > segment size (3), reverse all 3 valid nodes. 10 -> 20 -> 30 becomes 30 -> 20 -> 10. There are no invalid nodes.
3

Example 3

Input:

head = [-1, -2, 0], K = 1

Output:

[-1,-2,0]

Note:

  1. Compaction: All nodes are invalid. List remains -1 -> -2 -> 0.
  2. Segment Reverse (K=1): No valid nodes. Invalid segment has 3 nodes. Reverse first 1 invalid node: -1 remains -1. List remains -1 -> -2 -> 0.

Constraints

Constraints & assumptions

  • The number of nodes in the linked list will be between 0 and 10^5.
  • Node values (value) will be integers between -10^9 and 10^9.
  • K will be an integer between 1 and 10^5.
  • The solution must operate in O(N) time complexity, where N is the number of nodes in the list.
  • The solution must operate in O(1) auxiliary space complexity (i.e., no extra data structures proportional to N, beyond a few pointers).
  • The ListNode class definition is provided and should be used.

What interviewers evaluate

  • Correctness: The solution correctly handles all edge cases, including empty lists, lists with only valid/invalid nodes, and K values larger than segment sizes.
  • Algorithm Efficiency: The solution achieves the optimal O(N) time and O(1) space complexity.
  • Code Structure and Readability: The code is well-organized, clean, and easy to understand, with appropriate use of helper functions if needed.
  • Pointer Manipulation Skills: Demonstrates robust understanding and careful handling of linked list pointers, especially during splitting, merging, and reversal operations.

Loading editor...