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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def partition(self, head: ListNode, x: int) -> ListNode:
8 less_head = ListNode()
9 greater_head = ListNode()
10 less, greater = less_head, greater_head
11
12 while head:
13 if head.val < x:
14 less.next = head
15 less = less.next
16 else:
17 greater.next = head
18 greater = greater.next
19 head = head.next
20
21 greater.next = None
22 less.next = greater_head.next
23 return less_head.nextThis Python solution uses two pointers: one for nodes less than x and another for nodes greater or equal to x. By connecting the two groups at the end, the list is partitioned as required.
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)
1class ListNode
This Java implementation utilizes the in-place rearrangement strategy with four pointers to keep track of the ends of two partitions, effectively handling connections to form the required result.