My quick sort solution


  • 0
    C

    Quick sort for linked-list.

    1. select the pivot, then split into two lists.
    2. sort two lists recursivly.
    3. concat two lists into one.

    But need some optimization which is shown in comment, or it will be TLE-.-

    class Solution {
        	public:
        		ListNode *sortList(ListNode *head) {
        			if (! head) return head;
        
        			QuickSort(&head, NULL);
        
        			return head;
        		}
        
        		void AppendNode(ListNode **last, ListNode **head, ListNode *node)
        		{
        			if (*last) (*last)->next = node;
        			else 
        			{
        				*last = node;
        				*head = node;
        			}
        		}
        
        		void QuickSort(ListNode **head, ListNode **end)
        		{
        			if (! *head || ! (*head)->next) return;
        
        			ListNode *pivot = *head;
        			ListNode *lt = NULL, *rt = NULL;
        			ListNode *lhead = NULL, *rhead = NULL;
        			ListNode **cur = head;
        			ListNode *tmp = NULL;
        			
        			while (*cur)
        			{
        				if ((*cur)->val < pivot->val)
        				{
        					AppendNode(<, &lhead, *cur);
        					lt = *cur;
        				}
        				else
        				{
        					AppendNode(&rt, &rhead, *cur);
        					rt = *cur;
        				}
        
        				tmp = *cur;
        				*cur = (*cur)->next;
        				tmp->next = NULL;
        			}
        
        			//sorting two sides
        			QuickSort(&lhead, &lt);
        			//optimize this part
        			ListNode **ckp = &rhead->next;
        			while (*ckp && (*ckp)->val == rhead->val) ckp = &(*ckp)->next;
        			QuickSort(ckp, &rt); //skip pivot 
        			//QuickSort(&rhead->next, &rt);
        
        			//concats two lists
        			if (lhead) 
        			{
        				*head = lhead;
        				lt->next = rhead;
        			}
        			else *head = rhead;
        			//now pivot in middle
        
        			//set last node (in case of changes)
        			if (end) *end = rt;
        		}
        };

  • 0
    S

    The optimization is very important. I failed a lot without that. Thank you very much for sharing.


Log in to reply
 

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