I have a non-recursive solution but I want to further reduce the run time? Any idea?


  • 0
    E
    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            
            if (!head)
                return head;
            
            int listLen = 0;
            for (ListNode *pos = head; pos; pos = pos->next)
                ++listLen;
            
            auto newHead = head;
            
            for (int partLen = 1; partLen <= listLen; partLen += partLen) {
                auto pos = newHead;
                newHead = nullptr;
                ListNode *prevNewEnd{};
                
                while (pos != nullptr) {
                    auto left = pos;
                    auto leftEnd = move(left, partLen);  
                    auto right = leftEnd;
                    auto rightEnd = move(right, partLen);
                    pos = rightEnd;
                    ListNode *newEnd{};
                    auto p = merge(left, leftEnd, right, rightEnd, &newEnd);
                    
                    if (prevNewEnd)
                        prevNewEnd->next = p;
                        
                    prevNewEnd = newEnd;
                    
                    if (!newHead)
                        newHead = p;
                }
            }
            
            return newHead;
        }
        
        ListNode* merge(ListNode *leftHead, 
                        ListNode *leftEnd, 
                        ListNode *rightHead, 
                        ListNode *rightEnd,
                        ListNode **newEnd) {
            
            auto left  = leftHead;
            auto right = rightHead;
            ListNode head(0);
            auto writer = &head;
            
            ListNode *newHead{};
            
            while (left != leftEnd || right != rightEnd) {
                if (left != leftEnd && right != rightEnd) {
                    if(left->val <= right->val) {
                        writer->next = left;
                        left = left->next;
                    } else {
                        writer->next = right;
                        right = right->next;
                    }
                } else if (left != leftEnd) {
                    writer->next = left;
                    left = left->next;
                } else if (right != rightEnd) {
                    writer->next = right;
                    right = right->next;
                } else
                    break;
                
                writer = writer->next;
                
                if (!newHead)
                    newHead = writer;
            } 
            
            writer->next = rightEnd;
            *newEnd = writer;
            return newHead;
        }
       
        
        ListNode* move(ListNode *head, int step) {
            ListNode *pos = head;
            while (step-- > 0 && pos)
                pos = pos->next;
            return pos;
        }
    };

Log in to reply
 

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