Leetcode 86. Partition List

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

Set two pointers, one to point at insert position, another do scan to get wanted nodes. Or just part the list into two parts.

Solution 1:

# T:O(n) S:O(1)
class Solution:
    # @param {ListNode} head
    # @param {integer} x
    # @return {ListNode}
    def partition(self, head, x):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        p, q = dummy, head
        while True:
            while q.next and p.next.val < x:
                p = p.next
                q = q.next
            while q.next and q.next.val >= x:
                q = q.next
            if not q.next:
                return dummy.next
            else:
                temp = q.next
                q.next = temp.next
                temp.next = p.next
                p.next = temp
                p = p.next
        return dummy.next

Run Time: 64 ms

Solution 2:

# T:O(n) S:O(1)
class Solution:
    # @param head, a ListNode
    # @param x, an integer
    # @return a ListNode
    def partition(self, head, x):
        dummySmaller, dummyGreater = ListNode(-1), ListNode(-1)
        smaller, greater = dummySmaller, dummyGreater
        
        while head:
            if head.val < x:
                smaller.next = head
                smaller = smaller.next
            else:
                greater.next = head
                greater = greater.next
            head = head.next
            
        smaller.next = dummyGreater.next
        greater.next = None
        
        return dummySmaller.next

Run Time: 72 ms