c++ merge sort solution


  • 0
    E

    Here is my merge sort solution, using two pointers to find the middle of linked list, and merge two lists using ListNode* tail.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* merge(ListNode* left, ListNode* right){
            if(!left && !right) return NULL;
            else if(!left && right) return right;
            else if(!right && left) return left;
            
            ListNode* head;
            ListNode* tail;
            if(left->val < right->val) {
                head = left;
                left = left->next;
                tail = head;
            }
            else {
                head = right;
                right = right->next;
                tail = head;
            }
            
            while(left && right){
                if(left->val <= right->val) {
                    tail->next = left;
                    left = left->next;
                }
                else {
                    tail->next = right;
                    right = right->next;
                }
                tail = tail->next;
            }
            if(left && !right) tail->next = left;
            else if(!left && right) tail->next = right;
            return head;
        }
        ListNode* mergesort(ListNode* head){
            if(!head) return NULL;
            
            ListNode* slow = head;
            ListNode* fast = head;
            ListNode* pre = head;
            
            while(fast && fast->next){
                pre = slow;
                slow = slow->next;
                fast = fast->next->next;
            }
            
            // only one node in list
            if(!slow->next && slow==pre) return head;
            // only two nodes in list
            else if(!slow->next){
                if(pre->val <= slow->val) return head;
                else{
                    pre->next = NULL;
                    slow->next = pre;
                    return slow;
                }
            }
            
            pre->next = NULL;
            
            head = mergesort(head);
            slow = mergesort(slow);
            return merge(head,slow);
        }
        ListNode* sortList(ListNode* head) {
            return mergesort(head);
        }
    };
    

Log in to reply
 

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