python straight forward solution


  • 0

    The main idea is as follows:

    • find the position of the value that greater or equal than x, using two pointer bigpre and bigcur to record the previous position and current position in order to make an insertion.
    • find the value less than x behind bigcur and using two pointer to record the positions smallpre and smallcur.
    def partition(self, head, x):
            # find the first element that >=x
            if not head or not head.next:
                return head
            
            # to aviod the [2,1,1] the bigpre is None
            newhead=ListNode(-1)
            newhead.next=head
            # record the prenode and curnode of the bigger value
            bigpre=newhead
            bigcur=head
            
            # find the bigger position
            while bigcur:
                if bigcur.val>=x:
                    break
                bigpre=bigcur
                bigcur=bigcur.next
            # not find return directly
            if not bigcur:
                return head
            
            # find the value less than x
            # also using two pointer record the value
            smallpre=None
            smallcur=bigcur
            while smallcur:
                # if find, then change the pointer
                # if you can't understand what doing following
                # draw a graph 
                if smallcur.val<x:
                    # record the possible change value
                    pnext=smallcur.next
                    # insert the small value
                    bigpre.next=smallcur
                    # insert complete
                    smallcur.next=bigcur
                    # update delete small value pointer
                    smallpre.next=pnext
                    # update the pre pointer of bigger part
                    bigpre=smallcur
                    # finally update the cur of small
                    smallcur=pnext
                else:
                    smallpre=smallcur
                    smallcur=smallcur.next
            
            return newhead.next
    

Log in to reply
 

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