Python one pass and inplace solution, O(1) space.


  • 0
    P
    class Solution:
        # @param head, a ListNode
        # @param x, an integer
        # @return a ListNode
        def partition(self, head, x):
            if not head or not head.next:
                return head
            p = first = ListNode(0)
            first.next = head
            q = p.next
            while q:
                if q.val >= x:
                    rp = q
                    r = rp.next
                    while r:
                        if r.val >= x:
                            rp = r
                            r = r.next
                        else:
                            break
                    if not r:
                        break
                    p.next = r
                    rp.next = r.next
                    r.next = q
                    q = p.next
                else:
                    p = q
                    q = q.next
            return first.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.