My C++ solution (10ms) two versions (one maintains a single list and the other maintains two )

  • 0

    // Single list version (seems a little bit faster)

    class Solution {
    ListNode *partition(ListNode *head, int x) {
    ListNode dummyHead(0);
    ListNode *lastLNode, *lastGENode, *curNode, *newGENode ;

        lastLNode = curNode = &dummyHead; = head;
            while(curNode->next && curNode->next->val >= x) curNode = curNode->next; // find the last Greater or equal (GE) node;
            lastGENode = curNode;
            while(curNode->next && curNode->next->val < x) curNode = curNode->next; // find the new last Less (L) node;
            if(lastGENode == lastLNode) lastLNode = curNode; // for the first iteration, there might be no GE nodes at the beginning of the list, then we just update lastLNode
            { // otherwise, we need to cut the sub-linK (with nodes less than x) from lastGENode->next to curNode and insert it to lastLNode->next and current->next  
                newGENode = curNode->next;
                curNode->next = lastLNode->next;
                lastLNode->next = lastGENode->next;
                lastGENode->next = newGENode;
                lastLNode = curNode;
                curNode = lastGENode;


    // two lists version (much simpler)

     ListNode LHead(0), RHead(0);
      ListNode *curNode = head, *LPt = &LHead, *RPt = &RHead;
          if(curNode->val < x) {LPt = (LPt->next = curNode);}
          else                 {RPt = (RPt->next = curNode);}
          curNode = curNode->next;
      LPt->next =;
      RPt->next = NULL;

  • 0

    I like your second version very much. It is quite simple and compact. I am a new learner, and hope to learn from all of you.

Log in to reply

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