Share simple FFT kinda solution


  • 0
    B
    class Solution {
    public:
        ListNode* halfSort(ListNode* start, ListNode* end)
        {
            if(start == NULL || start == end || start->next == end)
            {
                return start;
            }
            ListNode* target = start;
            ListNode* curser = target;
            while(curser->next != end)
            {
                if(curser->next->val< target->val)
                {
                    ListNode* temp = curser->next;
                    curser->next = temp->next;
                    temp->next = start;
                    start = temp;
                }
                else
                {
                    curser = curser->next;
                }
            }
            start = halfSort(start, target);
            while(target->next != end && target->next->val == target->val)
            {
                target=target->next;
            }
            target->next = halfSort(target->next, end);
            return start;
        }
        
        ListNode* sortList(ListNode* head) {
            return halfSort(head, NULL);
        }
    };

  • 0
    V

    Worst-case running time of quicksort is O(n^2), isn't it?


  • 0
    B

    You are right. This is like a quick sort. Should have used merge sort for this. Thanks.


  • 0
    M

    I think since the problem requires constant space, recursion cannot be used here.


Log in to reply
 

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