Combination of Merge2List & 2-Pointers


  • 0
    /**
     * 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 || !head->next)  return head;
            ListNode *mid=head, *tail=head->next;
            while(tail && tail->next)  { mid=mid->next; tail=tail->next->next; }
            ListNode* left=head, *right=mid->next;
            mid->next=NULL;
            ListNode* sort_left=sortList(left);
            ListNode* sort_right=sortList(right);
            return help(sort_left, sort_right);
        }
        
        ListNode* help(ListNode* left, ListNode* right){
            ListNode* result=new ListNode(-1);
            ListNode* cur=result;
            while(left && right){
                if(left->val<=right->val) {
                    cur->next=left;  left=left->next;
                }else{
                    cur->next=right; right=right->next;
                }
                cur=cur->next;
            }
            if(left)    cur->next=left;
            if(right)   cur->next=right;
            return result->next;
        }
    };

  • 0
    2

    First check the special cases : NULL or SingleNode

    The merge function should be carefully implemented ...

    /**
     * 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) {
            /** bugs here */
            if(!head || !head->next)  return head;
            
            ListNode* dummy = new ListNode(INT_MIN);
            dummy->next = head;
            ListNode* slow = dummy, * fast = dummy;
            while(fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            ListNode* right_half = slow->next;
            slow->next = NULL;
            
            ListNode* left = sortList(dummy->next);
            ListNode* right = sortList(right_half);
            
            return mergeList(left, right);
        }
        
        ListNode* mergeList(ListNode* left, ListNode* right) {
            ListNode* dummy = new ListNode(INT_MIN);
            ListNode* cur = dummy;
            while(left && right) {
                if(left->val < right->val) {
                    cur->next = left;
                    left = left->next;
                } 
                else {
                    cur->next = right;
                    right = right->next;
                }
                /** bugs here */
                cur = cur->next;
            }
            if(left)  cur->next = left;
            if(right) cur->next = right;
            return dummy->next;
        }
    };

Log in to reply
 

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