Pls help as TLE (QuickSort and the algorithm seems okay while test locally)


  • 1
    S
    class Solution {
    
    public:
    
            void sortlist_operation(ListNode *begin, ListNode *end) {
    
            ListNode *target, *left, *right, *test_next, *test;
        
            target = begin->next;
        
            if (target->next == end) {
                // Only one element
                // Do nothing
            }
            else {
                test = target->next;
                target->next = NULL;
                left = target;
                right = target;    
                while (test != end) {
                    test_next = test->next;
                    if (test->val < target->val) {
                        test->next = left;
                        left = test;
                    }
                    else {
                        right->next = test;
                        right = test;
                        right->next = NULL;
                    }
                    test = test_next;
                }
                right->next = end;
                begin->next = left;
                if (begin->next != target) {
                    sortlist_operation(begin, target);
                }
                if (target->next != end) {
                    sortlist_operation(target, end);
                }
            }
        }
        ListNode *sortList(ListNode *head) {
            if (head == NULL) {
                return head;
            }
            struct ListNode head_nil(0);
            (&head_nil)->next = head;
        
            sortlist_operation((&head_nil), NULL);
            return (&head_nil)->next;
        }
    };

Log in to reply
 

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