
Problem Statement
When provided with a linked list and a value x
, the task is to rearrange the nodes in such a way that all nodes with values less than x
appear before any node with a value greater than or equal to x
in the list. During this rearrangement, it's critical to maintain the original relative order of the nodes that fall into these two categories (less than x
and greater than or equal to x
). Essentially, it involves segregating the linked list into two parts based on the criteria defined by x
, while ensuring that the order of elements within these segregated parts remains unchanged.
Examples
Example 1
Input:
head = [1,4,3,2,5,2], x = 3
Output:
[1,2,2,4,3,5]
Example 2
Input:
head = [2,1], x = 2
Output:
[1,2]
Constraints
- The number of nodes in the list is in the range
[0, 200]
. -100 <= Node.val <= 100
-200 <= x <= 200
Approach and Intuition
Given the nature of the problem, the intuitive approach is to effectively manage two sub-lists and then concatenate them:
Initialize Two Placeholder Nodes: Create two new linked list heads, one for elements less than
x
(let’s call itlessHead
) and another for elements greater than or equal tox
(greaterHead
). These will act as starting points to build the two sub-lists.Iterate Through the Original List: Traverse the original linked list node by node.
- If a node’s value is less than
x
, append it to thelessHead
list. - If a node’s value is greater than or equal to
x
, append it to thegreaterHead
list.
- If a node’s value is less than
Maintain Order Within Sub-lists: It’s important to add the current node to the end of the respective sub-lists to preserve the relative order of nodes. This can be managed by maintaining a pointer to the tail of both
lessHead
andgreaterHead
, updating it each time a new node is added.Merge the Two Sub-lists: After the original list has been completely traversed, connect the end of the
lessHead
sub-list to the start of thegreaterHead
sub-list.Consider Edge Cases: The algorithm should handle cases with empty lists, lists where all elements are the same, and lists where all elements are already partitioned correctly. This ensures that the result always adheres to the constraints and conditions provided.
By following this approach, the linked list is efficiently partitioned, guaranteeing that nodes less than x
are positioned before nodes greater than or equal to x
, while their original relative order is preserved. This technique leverages direct linkage manipulations which are optimal for operations in linked lists, avoiding unnecessary use of additional space or complex data structures.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
ListNode* separate(ListNode* node, int pivot) {
ListNode* less_head = new ListNode(0);
ListNode* less_tail = less_head;
ListNode* greater_head = new ListNode(0);
ListNode* greater_tail = greater_head;
while (node != NULL) {
if (node->val < pivot) {
less_tail->next = node;
less_tail = less_tail->next;
} else {
greater_tail->next = node;
greater_tail = greater_tail->next;
}
node = node->next;
}
greater_tail->next = NULL;
less_tail->next = greater_head->next;
return less_head->next;
}
};
The provided C++ solution defines a method named separate
inside a Solution
class, which aims to partition a linked list around a given pivot value. The method accepts a pointer to the head of the list (ListNode* node
) and an integer (pivot
) representing the pivot value. The list nodes with values less than the pivot are moved to one linked list, and those with values greater or equal are moved to another.
To achieve this partition:
- Initialize two dummy head nodes,
less_head
andgreater_head
, to simplify node connection without handling special cases for the head node. - Use two pointers,
less_tail
andgreater_tail
, to maintain the ends of the two growing lists (less than pivot and greater/equal to pivot).
During iteration through the input list:
- Nodes with values less than the pivot are appended to the list headed by
less_head
. - Nodes with values greater or equal to the pivot are appended to the list headed by
greater_head
. - At the end of the iteration, ensure the list headed by
greater_tail
is properly terminated with aNULL
to signify the end of the list.
Finally:
- Connect the list containing nodes less than the pivot to the list of nodes greater than or equal to the pivot.
- Return the head of the modified list, which effectively omits the initial dummy node (
less_head->next
).
This method efficiently partitions the linked list in one pass, using constant space for pointers and ensuring that nodes are rearranged without creating new ones, just re-linking the existing nodes according to their values relative to the pivot
.
class Solution {
public ListNode split(ListNode start, int pivot) {
ListNode lowHead = new ListNode(0);
ListNode lowTail = lowHead;
ListNode highHead = new ListNode(0);
ListNode highTail = highHead;
while (start != null) {
if (start.val < pivot) {
lowTail.next = start;
lowTail = lowTail.next;
} else {
highTail.next = start;
highTail = highTail.next;
}
start = start.next;
}
highTail.next = null;
lowTail.next = highHead.next;
return lowHead.next;
}
}
This Java solution addresses the problem of partitioning a linked list around a given pivot value, such that all nodes less than the pivot come before all nodes greater than or equal to the pivot. The function split
is defined to handle this logic and takes two parameters: the head of the list (start
) and the pivot value (pivot
).
Here's how the solution operates:
- Two dummy nodes,
lowHead
andhighHead
, are created to form the beginning of two separate linked lists: one for values lower than the pivot and another for values higher or equal. - Two pointers,
lowTail
andhighTail
, start at these dummy nodes and help in building the two lists. - As you iterate through the original list, each node is either added to the end of the
lowTail
list (if its value is less than the pivot) or to thehighTail
list (if its value is greater than or equal). - This iteration continues until all elements of the original list are examined.
- The list of higher or equal values must have its last node pointing to null to denote the end of the list.
- To merge the two lists, set the
next
pointer of thelowTail
(end of lower value list) to the head of the higher values list, which starts right after the dummy nodehighHead
. - Finally, return the head of the modified list, which is now properly partitioned, by pointing to the next of
lowHead
.
This method effectively re-arranges the nodes of the original list without needing additional memory for new nodes, thereby providing an efficient in-place solution.
struct ListNode* separate(struct ListNode* start, int threshold) {
struct ListNode* less_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
less_than_head->next = NULL;
struct ListNode* less = less_than_head;
struct ListNode* greater_than_head = (struct ListNode*)malloc(sizeof(struct ListNode));
greater_than_head->next = NULL;
struct ListNode* greater = greater_than_head;
while (start != NULL) {
if (start->val < threshold) {
less->next = start;
less = less->next;
} else {
greater->next = start;
greater = greater->next;
}
start = start->next;
}
greater->next = NULL;
less->next = greater_than_head->next;
return less_than_head->next;
}
The given C language code defines a function separate
that partitions a linked list based on a threshold value. The function accepts a linked list (start
) and an integer (threshold
) as parameters. The goal is to rearrange the linked list so that all nodes with values less than the threshold
are moved before nodes with values equal to or greater than the threshold
.
- The function initializes two dummy head nodes:
less_than_head
for the list of elements less than the threshold andgreater_than_head
for the list of elements equal to or greater than the threshold. - It iterates through the input list, and segregates nodes into the
less
andgreater
lists based on their values compared to the threshold. - After the iteration, ensure that the last node in the
greater
list points toNULL
to mark the end of that list. - The
next
of the lastless
node points to the first element of thegreater_than_head
list to concatenate the two lists. - Finally, return the
next
of theless_than_head
which is effectively the head of the newly arranged linked list.
This rearrangement is done in-place, and the algorithm efficiently partitions the nodes with a single traversal through the original list. The approach ensures that the relative order of nodes in each partition is preserved and it uses constant space for the pointers, excluding the input list nodes themselves.
var splitList = function (node, pivot) {
var lowStart = new ListNode(0);
var lowEnd = lowStart;
var highStart = new ListNode(0);
var highEnd = highStart;
while (node != null) {
if (node.val < pivot) {
lowEnd.next = node;
lowEnd = lowEnd.next;
} else {
highEnd.next = node;
highEnd = highEnd.next;
}
node = node.next;
}
highEnd.next = null;
lowEnd.next = highStart.next;
return lowStart.next;
};
The JavaScript function "splitList" is designed to partition a linked list around a pivot value. It rearranges the list so that all nodes with values less than the pivot come before nodes with values greater than or equal to the pivot. Here's a breakdown of how it accomplishes this:
- Initialize two dummy nodes,
lowStart
andhighStart
, which act as the starting points for the two parts of the split list. - Utilize two pointers,
lowEnd
andhighEnd
, which help in appending nodes to the respective parts. - Traverse through the linked list using a while loop. During each iteration, compare the current node's value with the pivot:
- If the node's value is less than the pivot, append it to the
lowEnd
. - Otherwise, append it to the
highEnd
.
- If the node's value is less than the pivot, append it to the
- After exiting the loop, set the next pointer of
highEnd
to null to mark the end of the high part of the list. - Connect the end of the low part list to the beginning of the high part list.
- Return the next node of
lowStart
as it points to the head of the newly arranged list.
This method effectively partitions the list with a time complexity of O(n) and does not require additional space beyond the few temporary pointers, making it space efficient.
class Solution(object):
def rearrangeNodes(self, start: ListNode, pivot: int) -> ListNode:
# Initialize two list heads and current pointers
lower = lower_head = ListNode(0)
higher = higher_head = ListNode(0)
while start:
# Distribute nodes into lower or higher based on their value
if start.val < pivot:
lower.next = start
lower = lower.next
else:
higher.next = start
higher = higher.next
# Proceed to next node in original list
start = start.next
# Terminate the higher value list
higher.next = None
# Connect lower values list to higher values list
lower.next = higher_head.next
return lower_head.next
The provided Python code defines a function that partitions a linked list around a given pivot value. Each node in the linked list has a numeric value, and the function rearranges the nodes such that all nodes with values less than the pivot are moved before nodes with values greater than or equal to the pivot. The rearrangement is performed using the following steps:
- Initialize two dummy head nodes,
lower_head
andhigher_head
, to help in segregating nodes into two lists: one for values lower than the pivot and one for values higher or equal. - Traverse through the original list. Depending on whether the node's value is less than the pivot, append it to the end of the
lower
list, or otherwise to thehigher
list. - Properly manage the next pointers. After evaluating a node, proceed to the next node in the list.
- Ensure that the
higher
list is terminated properly to avoid any potential cyclic linking in the list. - Connect the
lower
list to thehigher
list by setting the next pointer of the last node of thelower
list to the first node of thehigher
list. - Return the next node of
lower_head
as the new head of the rearranged list, excluding the dummy head.
This solution efficiently partitions the list with a single traversal, resulting in a time complexity of O(n), where n is the number of nodes in the list, and it uses O(1) extra space since no additional nodes are created, only pointers are reassigned.
No comments yet.