Problem Statement in English

You’re given the head of a linked list and a value x. Partition the linked list such that all nodes less than x come before nodes greater than or equal to x.

Ensure that the original relative order of the nodes in each of the two partitions is preserved.

Approach

Since the question says we need to preserve the original order of the nodes while essentially placing them in either a “less than x” or “greater than or equal to x” partition, we can use two separate linked lists to achieve this.

One linked list will hold all the nodes with values less than x, and the other will hold all the nodes with values greater than or equal to x.

As we iterate through the original linked list, we will append each node to the appropriate new linked list based on its value. After processing all nodes, we will connect the two lists together.

In order to be able to easily stitch them together, before we start iterating, we will create two dummy nodes to serve as the heads of the two new linked lists. This will help us avoid edge cases when one of the lists is empty.

Finally, we will return the head of the new combined linked list, which will be the next node of the dummy node for the “less than x” list.

And we’re done!

Solution in Python


class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        before_head = ListNode(0)
        before = before_head
        
        after_head = ListNode(0)
        after = after_head

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_head.next

        return before_head.next

Complexity

  • Time: $O(n)$
    Since we traverse the entire linked list once, the time complexity is linear with respect to the number of nodes in the list.

  • Space: $O(1)$
    Since we are using a constant amount of extra space for the two new linked lists (before and after), the space complexity is constant.

And we are done.