Partition List

Challenge

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

The order of the initial linked list must be preserved.

Solution

from copy import deepcopy
class Solution:
    
    def add_to_list(self, head, node,x):
        node.next = None
        if head is None and node.val < x:
            self.left_part = node
            self.left_tail = node
            return
        elif head is None and node.val >= x:
            self.right_part = node
            self.right_tail = node
            return
        if head == self.left_part:
            self.left_tail.next = node
            self.left_tail = node
        if head == self.right_part:
            self.right_tail.next = node
            self.right_tail = node
        
    def partition(self, head: ListNode, x: int) -> ListNode:
        self.left_part = None
        self.right_part = None
        tmp = head
        while tmp:
            tmp_cpy = deepcopy(tmp)
            if tmp.val < x:
                self.add_to_list(self.left_part, tmp_cpy,x)
            else:
                self.add_to_list(self.right_part, tmp_cpy,x)
            tmp = tmp.next
        tmp = self.left_part
        if not tmp:
            return self.right_part
        self.left_tail.next = self.right_part
        return self.left_part

Time complexity: O(n)
Space complexity: O(1)

Challenge#

Solution#

Challenge

Solution