Group and Relocate Linked List Elements
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.
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:
val is equal to k are moved to the end of the list.val is not equal to k must be preserved.val is equal to k must also be preserved.Your solution should aim for optimal time and space complexity.
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:
ListNode representing the head of the rearranged linked list. If the input list is empty, return null.head is null, the function should return null.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.k values: If no nodes in the list have val == k, the list should remain unchanged.Examples
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.
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.
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
N) will be between 0 and 10^5.Node.val) will be between 0 and 10^9.k will be between 0 and 10^9.ListNode objects. The solution should modify the existing list structure by re-pointing next pointers.k.Loading editor...