Concise C++ solution


  • 0
    R
      ListNode* partition(ListNode* head, int x) {
            if (!head || !head->next)
                return head;
            
            ListNode* preHead = new ListNode(-1);
            preHead->next = head;
            ListNode* curNode, *secPart, *secPartHead, *firPart = preHead;
            
            // Go through the list to find the 1st node whose element is >= x
            for (curNode = head; curNode->val < x && curNode->next; curNode = curNode->next)
                firPart = firPart->next;
            
            secPartHead = secPart = curNode;    // assign the 1st node as head of 2nd part
            curNode = curNode->next;
            while (curNode)
            {
                if (curNode->val < x)
                    // link curNode to the end of firPart, then firPart iterates to current position    
                    firPart = firPart->next = curNode;
                else
                    secPart = secPart->next = curNode;
                curNode = curNode->next;
            }
            firPart->next = secPartHead;    // link 2 parts at last
            secPart->next = nullptr;
            firPart = preHead->next;
            delete preHead;
            return firPart;
        }

Log in to reply
 

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