Frontend School

Group and Relocate Linked List Elements

DSA
hard

Group and Relocate Linked List Elements

Hard
Linked List
Two Pointers
In-place
Data Structures

Overview

In financial systems like PhonePe, transaction logs and event streams are crucial for auditing, analysis, and processing. Often, these logs are structured as sequences of data, which can be efficiently represented by linked lists. A common operational requirement is to segregate or prioritize certain types of events or transactions. For instance, high-priority or problematic transactions might need to be moved to the end of a processing queue for later review, while ensuring the order of other transactions remains undisturbed.

This problem challenges you to implement an efficient algorithm to rearrange a linked list representing a sequence of data, such that all elements matching a specific value are relocated to the end, preserving the relative order of all other elements.

What you need to do / Task

Implement the function groupAndRelocate that takes the head of a singly linked list and an integer k as input. The function should rearrange the linked list in-place such that:

  1. All nodes whose val is equal to k are moved to the end of the list.
  2. The relative order of all nodes whose val is not equal to k must be preserved.
  3. The relative order of all nodes whose val is equal to k must also be preserved.

Your solution should aim for optimal time and space complexity.

Input & output

Input:

  • head: A ListNode representing the head of the singly linked list. Each node has an integer val and a next pointer to the subsequent node.
  • k: An integer representing the target value to be relocated to the end.

Output:

  • Return a ListNode representing the head of the rearranged linked list. If the input list is empty, return null.

Clarifications

  • Empty List: If head is null, the function should return null.
  • Single Node List: Handle cases where the list contains only one node.
  • All k values: If all nodes in the list have val == k, their relative order should remain unchanged, and they should still constitute the entire list.
  • No k values: If no nodes in the list have val == k, the list should remain unchanged.

Examples

1

Example 1

Input:

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

Output:

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

Note:

Nodes with value 4 are moved to the end. The original order of [1, 3, 2, 5] (non-k elements) is preserved. The original order of [4, 4] (k elements) is also preserved.

2

Example 2

Input:

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

Output:

[1, 2, 3, 4, 5]

Note:

No nodes with value 6 are found, so the list remains unchanged.

3

Example 3

Input:

head = [7, 7, 1, 7, 2], k = 7

Output:

[1, 2, 7, 7, 7]

Note:

Nodes with value 7 are moved to the end. The original order of [1, 2] (non-k elements) is preserved. The original order of [7, 7, 7] (k elements) is also preserved.

Constraints

Constraints & assumptions

  • The number of nodes in the list (N) will be between 0 and 10^5.
  • Node values (Node.val) will be between 0 and 10^9.
  • The target value k will be between 0 and 10^9.
  • The list is singly linked.

Out of scope

  • Creating new ListNode objects. The solution should modify the existing list structure by re-pointing next pointers.

What interviewers evaluate

  • Correctness: The solution correctly partitions the list and preserves the relative order of both groups of elements.
  • Efficiency: The algorithm achieves optimal time complexity (linear time) and space complexity (constant space).
  • Edge Case Handling: Robustness against various edge cases, including empty lists, single-node lists, and lists where all or no elements match k.
  • Code Quality: Readability, maintainability, and clarity of the implemented logic.

Loading editor...