Skip to content

86. Partition List

Difficulty Topics

Description

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:

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

Solution

partition-list.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        front = cFront = ListNode(-1)
        back = cBack = ListNode(-1)

        while head:
            v = head.val
            if v < x:
                front.next = ListNode(v)
                front = front.next
            else:
                back.next = ListNode(v)
                back = back.next

            head = head.next

        front.next = None
        front.next = cBack.next

        return cFront.next