6ms, one pass solution with dummy head


  • 0
    N

    Whenever we modify the structure of the list, we declare a dummy node. To partition the list, we need to define the node before and after the target node, move the target node, and reconnect the list.

        ListNode* partition(ListNode* head, int x) {
            if(!head || !head->next)
                return head;
            ListNode* dummy = new ListNode(0);
            dummy->next = head;
            ListNode* preGE = dummy;
            ListNode* GE = NULL;
            
            while(head){
                if(head->val >= x){
                    GE = head;
                    break;
                }
                preGE = head;
                head = head->next;
            }
            
            if(!head)
                return dummy->next;
            ListNode* preSmaller = preGE;    
            while(head){
                if(head->val >= x){
                    preSmaller = head;
                    head = head->next;
                    continue;
                }    
                ListNode* smaller = head;
                head = head->next;
                smaller->next = GE;
                preGE->next = smaller;
                preGE = smaller;
                preSmaller->next = head;
            }
            
            return dummy->next;
        }
    '''

Log in to reply
 

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