C++ quick sort 3 way partition (56ms)


  • 0
    O

    still vulnerable to already sorted list, but is adaptive in the case of sorting with few unique keys.

    divide nodes into 3 groups:

    1. node->val < pivot.val

    2. node->val == pivot->val

    3. node->val > pivot->val

      ListNode* sortList(ListNode* head)
      {
      if (!head) return nullptr;
      ListNode dummyL{0};
      ListNode dummyR{0};
      ListNode dummyM{0};
      ListNode *tempL = &dummyL;
      ListNode *tempR = &dummyR;
      ListNode *tempM = &dummyM;
      tempM->next = head;
      tempM = tempM->next;
      ListNode *current = head->next;
      while (current) {
      if (current->val < head->val) {
      tempL->next = current;
      tempL = tempL->next;
      } else if (current->val == head->val) {
      tempM->next = current;
      tempM = tempM->next;
      } else {
      tempR->next = current;
      tempR = tempR->next;
      }
      current = current->next;
      }
      tempL->next = nullptr;
      dummyL.next = sortList(dummyL.next);
      tempR->next = nullptr;
      dummyR.next = sortList(dummyR.next);
      tempL = dummyL.next;
      if (tempL) {
      while (tempL->next)
      tempL = tempL->next;
      tempL->next = dummyM.next;
      tempM->next = dummyR.next;
      return dummyL.next;
      } else {
      dummyL.next = dummyM.next;
      tempM->next = dummyR.next;
      return dummyL.next;
      }
      }


Log in to reply
 

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