QuickSort be accepted. And Runtime Error may be your program in the loop.


  • 1
    S

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      class Solution {
      public:
      ListNode
      sortList(ListNode* head) {

       if(head == NULL) {
           return head;
       }
      ListNode *h = head;
      
       ListNode *p = head->next;
      
      if(p == NULL){
      	return head;
      }
      
       ListNode *Btemp = NULL;
       ListNode *bt=NULL;
       
       ListNode *Atemp = NULL;
       ListNode *at=NULL;
       
       while(p){
           if(p->val < head->val){
               if(Btemp){
               bt->next = p;
               bt = bt->next;
               }
               else{
               Btemp = p;
               bt = Btemp;
               }
           }else if(p->val > head->val){
               if(Atemp){
               at->next = p;
               at = at->next;
               }
               else{
               Atemp = p;
               at = Atemp;
               }
           }else{
      		h->next = p;
      		h = h->next;
      	}
           p= p->next;
       }
      
      if(bt){
      bt->next = NULL;
      }
      if(at){
      at->next = NULL;
      }
      
      bt = sortList(Btemp);
      at = sortList(Atemp);
      
      h->next = at;
      if(bt){
      	ListNode *bl = bt;
      	while(bl->next){
      		bl = bl->next;
      	}
      	bl->next = head;
      }else{
      	bt = head;
      }
      
       return bt;
      

      }
      };


  • 0
    D

    It's quick sort, but doesn't ensure nlgn complexity since you always use head as pivot.

    Another post mentioned the test cases used for this question with similar strategy as yours.

    It's a good idea to move nodes smaller or bigger to 2 temporary lists, it won't be too complicated even using random pivot. I didn't thought this but just moved nodes back and forth in the original list with random pivot, which made my codes more complicated.


  • 0
    D

    Confused, what does "And Runtime Error may be your program in the loop." mean...?


Log in to reply
 

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