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.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 public ListNode partition(ListNode head, int x) {
9 ListNode lessHead = new ListNode(0);
10 ListNode greaterHead = new ListNode(0);
11 ListNode less = lessHead, greater = greaterHead;
12
13 while (head != null) {
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}This Java solution follows a similar strategy. By using dummy nodes for the less and greater lists, it maintains the original relative order of nodes and ensures that the solution remains 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)
1function ListNode
This JavaScript solution implements in-place node rearrangement to enforce the required partitioning, utilizing direct connections to achieve efficient management without additional space.