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.
1function ListNode(val, next = null) {
2 this.val = val;
3 this.next = next;
4}
5
6function partition(head, x) {
7 let lessHead = new ListNode(0);
8 let greaterHead = new ListNode(0);
9 let less = lessHead, greater = greaterHead;
10
11 while (head !== null) {
12 if (head.val < x) {
13 less.next = head;
14 less = less.next;
15 } else {
16 greater.next = head;
17 greater = greater.next;
18 }
19 head = head.next;
20 }
21 greater.next = null;
22 less.next = greaterHead.next;
23 return lessHead.next;
24}This JavaScript solution uses a very similar method as the previous languages. It effectively makes use of dummy nodes to keep track of the lesser and greater partitions, ensuring efficient traversal and recombination of the list.
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)
1#include
This C implementation uses four pointers to represent the start and end of the 'before' and 'after' lists. As we traverse the original list, we reattach nodes to these lists, eventually connecting them at the end.