86. Partition List (Python)

Related Topic

Linked-List. Two-Pointers.

Description

Given 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.

You should preserve the original relative order of the nodes in each of the two partitions.

Sample I/O

Example 1

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Methodology

Solution 1

We need to set a prev pointer to indicate the last node which less than target. We iterate the linked list until we find the current node is greater or equal than target and next node is less than target then we need to let prev node’s next pointer point to the current’s next node and update prev, we also need to let current node’s next pointer point to it’s next next node. Since there may be consective nodes that less than target, we need to keep tracking (do not updata head) until we find a node that greater or equal to target then we update head.

This may be hard to think, it would be easier if you draw on paper, here is an edge case 1->2->3->2->1 target is 3.

Solution 2

We can also create two linked lists l1, l2, l1 for value less than target and l2 for value greater or equal than target. After that, we just append the l2 to l1 and return the new linked list.

Code (solution 1)

    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head or not head.next: return head
        dummy_head = prv = ListNode("inf")
        prv.next = head
        while head and head.next:
            if head.val >= x and head.next.val<x:
                temp = head.next.next
                head.next.next = prv.next
                prv.next = head.next
                head.next = temp
            else:
                head = head.next
            if prv.next.val < x:
                prv=prv.next
        return dummy_head.next

BigO

Iterate the linked list once, so total time complexity is O(n)

Code (solution 2)

    def partition(self, head, x):
        h1 = l1 = ListNode(0)
        h2 = l2 = ListNode(0)
        while head:
            if head.val < x:
                l1.next = head
                l1 = l1.next
            else:
                l2.next = head
                l2 = l2.next
            head = head.next
        l2.next = None
        l1.next = h2.next
        return h1.next

BigO

Iterate the linked list once, so total time complexity is O(n)