DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Partition List

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:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def lessThan(self, head, x):
        if not head:
            return head
        if head.val >= x:
            return self.lessThan(head.next, x)
        newhead = TreeNode(val = head.val)
        newhead.next = self.lessThan(head.next, x)
        return newhead

    def greaterThan(self, head, x):
        if not head:
            return head
        if head.val < x:
            return self.greaterThan(head.next, x)
        newhead = TreeNode(val = head.val)
        newhead.next = self.greaterThan(head.next, x)
        return newhead

    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left = self.lessThan(head, x)
        right = self.greaterThan(head, x)
        if not left:
            return right
        curr = left
        while curr and curr.next:
            curr = curr.next
        curr.next = right
        return left
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more