Compact and Segment Reverse Linked List
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.
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:
K nodes in the valid segment. Then, reverse the first K nodes in the invalid segment.
K nodes, reverse all of them.K nodes, reverse all of them.Your function should return the head of the reordered and modified linked list.
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:
ListNode object representing the head of the modified linked list after compaction and segment reversal. Returns null if the input list was empty.head = null) should result in null output.K is larger than the number of nodes in a segment, you should reverse all nodes present in that segment.Examples
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 -> 3 -> 4 -> 6 -> 7 -> -2 -> -5 -> 01 -> 3 becomes 3 -> 1): 3 -> 1 -> 4 -> 6 -> 7 -> -2 -> -5 -> 0-2 -> -5 becomes -5 -> -2): 3 -> 1 -> 4 -> 6 -> 7 -> -5 -> -2 -> 0Example 2
Input:
head = [10, 20, 30], K = 5
Output:
[30,20,10]
Note:
10 -> 20 -> 30.10 -> 20 -> 30 becomes 30 -> 20 -> 10. There are no invalid nodes.Example 3
Input:
head = [-1, -2, 0], K = 1
Output:
[-1,-2,0]
Note:
-1 -> -2 -> 0.-1 remains -1. List remains -1 -> -2 -> 0.Constraints
0 and 10^5.value) will be integers between -10^9 and 10^9.K will be an integer between 1 and 10^5.O(N) time complexity, where N is the number of nodes in the list.O(1) auxiliary space complexity (i.e., no extra data structures proportional to N, beyond a few pointers).ListNode class definition is provided and should be used.K values larger than segment sizes.O(N) time and O(1) space complexity.Loading editor...