Skip to content

86. Partition List

Problem

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.

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

Example 1:

Pasted image 20230818093551.png

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

  • The number of nodes in the list is in the range [0, 200].
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Solve

De-linked list and make new one

O(n)

Just throw away the linked list, I storing all data in a array and rebuild new one.

  • Loop through head to construct delink array that have all value at the same position of head list
  • Loop through the delink array twice to construct the result link list 
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        p = head
        delink = []
        while p:
            delink.append(p.val) 
            p = p.next
        newHead = None
        p = None
        for i in delink:
            if i >= x:
                continue
            if newHead is None:
                newHead = ListNode(i)
                p = newHead
                continue
            p.next = ListNode(i)
            p = p.next

        for i in delink:
            if i < x:
                continue
            if newHead is None:
                newHead = ListNode(i)
                p = newHead
                continue
            p.next = ListNode(i)
            p = p.next

        return newHead

Loop on linked list but still make new one

O(n)

The previous approach only loop through the list once, not randomly accessing it, so we can just use normal loop through provided head linked list using a pointer p variable.

To make it better, I using two temp Linked list to construct the result Linked list, so that I only need to loop through head once:

  • smaller: Contain all smaller node
  • equalOrBigger: Contain all the other node
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        p = head
        smaller = None
        equalOrBigger = None
        eSmall = None
        eBig = None
        while p:
            if p.val >= x:
                if equalOrBigger is None:
                    equalOrBigger = ListNode(p.val)
                    eBig = equalOrBigger
                else:
                    eBig.next = ListNode(p.val)
                    eBig = eBig.next
            else:
                if smaller is None:
                    smaller = ListNode(p.val)
                    eSmall = smaller
                else:
                    eSmall.next = ListNode(p.val)
                    eSmall = eSmall.next
            p = p.next
        if smaller is None:
            smaller = equalOrBigger
        else:
            eSmall.next = equalOrBigger
        return smaller

Loop on linked list and reused all the old provided ListNode

O(n)

Instead of create new ListNode, we can directly using p as our node
Still, we need to store p by temp so that our change doesn’t affect the loop code

        while p:
            temp = p
            p = p.next
            # <reuse logic on temp>

Final implementation

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        p = head
        smaller = None
        equalOrBigger = None
        eSmall = None
        eBig = None
        while p:
            temp = p
            p = p.next
            if temp.val >= x:
                if equalOrBigger is None:
                    equalOrBigger = temp
                    eBig = equalOrBigger
                else:
                    eBig.next = temp
                    eBig = eBig.next
            else:
                if smaller is None:
                    smaller = temp
                    eSmall = smaller
                else:
                    eSmall.next = temp
                    eSmall = eSmall.next
        if equalOrBigger is not None:
            eBig.next = None
        if smaller is None:
            smaller = equalOrBigger
        else:
            eSmall.next = equalOrBigger
        return smaller

Last update : September 17, 2023
Created : August 17, 2023