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


  • 0
    D

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

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

        lastLNode = curNode = &dummyHead;
        dummyHead.next = head;
        while(curNode->next)
        {
            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
            else
            { // 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;
            }
        }
        
        return dummyHead.next;
    }
    

    };

    // two lists version (much simpler)

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

  • 0
    A

    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.