Sponsored
Sponsored
This approach involves using two separate linked lists to store nodes that are less than x and nodes that are greater than or equal to x. You traverse the original list and attach each node to the appropriate list. Finally, you connect the two lists together to form the partitioned list.
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), as we only use a constant amount of extra space.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* partition(struct ListNode* head, int x) {
10 struct ListNode lessHead = {0, NULL}, greaterHead = {0, NULL};
11 struct ListNode *less = &lessHead, *greater = &greaterHead;
12
13 while (head) {
14 if (head->val < x) {
15 less->next = head;
16 less = less->next;
17 } else {
18 greater->next = head;
19 greater = greater->next;
20 }
21 head = head->next;
22 }
23 greater->next = NULL;
24 less->next = greaterHead.next;
25 return lessHead.next;
26}
27
28// Helper functions and testing code are omitted for brevity.This C implementation uses two dummy node pointers to build the 'less than x' and 'greater or equal to x' lists. It iterates through the original list only once, making the approach efficient.
This in-place rearrangement technique modifies the original list without the need of additional dummy nodes. This is accomplished by managing pointers to redefine segment connections efficiently.
Time Complexity: O(n)
Space Complexity: O(1)
1public class ListNode {
2 public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode Partition(ListNode head, int x) {
ListNode beforeStart = null, beforeEnd = null, afterStart = null, afterEnd = null;
while (head != null) {
ListNode next = head.next;
head.next = null;
if (head.val < x) {
if (beforeStart == null) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd.next = head;
beforeEnd = head;
}
} else {
if (afterStart == null) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd.next = head;
afterEnd = head;
}
}
head = next;
}
if (beforeStart == null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}
}This C# implementation uses in-place rearrangement with four pointers to effectively organize nodes less than x and greater than or equal to x, achieving optimal partitioning.