Approach #1 Partitioning (Accepted)
We want to move all nodes smaller than $$x$$ to the front of the list, without disturbing the rest of the nodes. This is equivalent to taking all nodes larger than or equal to $$x$$ and moving them to the back of the list. Therefore we can traverse the list to partition it into nodes with smaller value than $$x$$ and larger or equal value to $$x$$.
Given the linked list, we first create two empty lists to contain the smaller and larger nodes. Let these lists be known as larger and smaller. In order to merge the lists at the end of the procedure, we must also create pointers to keep track of the head of each list.
We iterate through the list. For each node we append it to smaller if the node value is smaller than $$x$$, and larger otherwise. When we reach the end of the list, we have two linked lists containing the partitioned list. The lists can be combined by appending the larger list to the smaller list, using the pointers we create in the beginning of the procedure. The resulting list is the successfully partitioned list.
class Solution: def partition(self, head, x): if head == None or head.next == None: # Special cases return head less = ListNode(None) # Dummy node more = ListNode(None) # Dummy node head_more = more # Pointer to keep track of the list head head_less = less # Pointer to keep track of the list head while head != None: if head.val < x: less.next = ListNode(head.val) less = less.next else: more.next = ListNode(head.val) more = more.next head = head.next # We always go to the next node. less.next = head_more.next # Combine the two lists. return head_less.next # Remember to skip the dummy node.
- Time complexity : $$O(n)$$. We iterate through the list exactly once, and the concatenation procedure is in constant time.
- Space complexity : $$O(n)$$. In the algorithm we generate a copy of each node in the list. Because we have $$2n$$, this reduces to $$O(n)$$ space. This algorithm can be modified to use $$n$$ space by mutating the list in place.