Problem statement

https://binarysearch.com/problems/Linked-List-Partitioning/

Solution

Variation of Leetcode 0086. Partition List, but we need 3 pointers, not 2.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def solve(self, head, k):
        d1 = LLNode(-1)
        d2 = LLNode(-1)
        d3 = LLNode(-1)
        p1, p2, p3 = d1, d2, d3
        while head:
            if head.val < k:
                p1.next = head
                p1 = p1.next
            elif head.val == k:
                p2.next = head
                p2 = p2.next
            else:
                p3.next = head
                p3 = p3.next
            head = head.next
            
        p1.next = d2.next
        p2.next = d3.next
        p3.next = None
        return d1.next