Problem statement

https://leetcode.com/problems/partition-list/

Solution

All we need to do is to create two dummy heads for two new lists and then traverse through original list and add elements. On each step we check if value of node is less than x or not. If it is less, append it to the end of the first list and move pointer p1, so it always points to the end of first list. If it is more than equal than x, move second pointer. In the end we have 4 pointers in the following order: d1->... -> p1 d2->... ->p2->, so what we need to do now is to add connection p1->d2 and also remove connection from p2.

Complexity

Time complexity is O(n) and space complexity is O(1).

Code

class Solution:
    def partition(self, head, x):
        d1 = ListNode(-1)
        d2 = ListNode(-1)
        p1, p2 = d1, d2
        while head:
            if head.val < x:
                p1.next = head
                p1 = p1.next
            else:
                p2.next = head
                p2 = p2.next
            head = head.next
            
        p1.next = d2.next
        p2.next = None
        return d1.next