C++, very clear solution


  • 0
    M

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      ListNode
      partition(ListNode* head, int x) {
      ListNode *pBeforeStart = NULL;
      ListNode *pBeforeEnd = NULL;
      ListNode *pAfterStart = NULL;
      ListNode *pAfterEnd = NULL;

       while(head) {
           ListNode *pNext = head->next;
           head->next = NULL;
           
           if (head->val < x) { // insert it into before
               if (pBeforeStart == NULL) {
                   pBeforeStart = head;
                   pBeforeEnd = pBeforeStart;
               } else {
                   pBeforeEnd->next = head;
                   pBeforeEnd = head;
               }
           } else { // insert after
               if (pAfterStart == NULL) {
                   pAfterStart = head;
                   pAfterEnd = pAfterStart;                    
               } else {
                   pAfterEnd->next = head;
                   pAfterEnd = head;                    
               }
           }
           head = pNext;
       }
       
       if (pBeforeStart == NULL) {
           return pAfterStart;
       }
       
       pBeforeEnd->next = pAfterStart;
       return pBeforeStart;
      

      }
      };


Log in to reply
 

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