21.Merge Two Sorted Lists 、23. Merge k Sorted Lists

21.Merge Two Sorted Lists

初始化一个指针作为开头，然后返回这个指针的next

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while(l1 && l2){
            if(l1->val <= l2->val){
                p->next = l1;
                p = p->next;
                l1 = l1->next;
            }
            else{
                p->next = l2;
                p = p->next;
                l2 = l2->next;
            }
        }
        if(l1)
            p->next = l1;
        else
            p->next = l2;
        return dummy->next;
    }
};

23. Merge k Sorted Lists

https://www.cnblogs.com/grandyang/p/4606710.html

这个是分治的思想

实质上就是每次合并一半的链表，且两两合并的链表按照一定间隔距离进行合并

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if(n <= 0)
            return NULL;
        while(n > 1){
            int k = (n + 1)/2;
            for(int i = 0;i < n/2;i++)
                lists[i] = mergeList(lists[i],lists[i + k]);
            n = k;
        }
        return lists[0];
    }
    ListNode* mergeList(ListNode* l1,ListNode* l2){
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        ListNode* head;
        if(l1->val < l2->val){
            head = l1;
            head->next = mergeList(l1->next,l2);
        }
        else{
            head = l2;
            head->next = mergeList(l1,l2->next);
        }
        return head; 
    }
};

自己写的：

用非递归也可以合并两个链表。

k = (n + 1)/2中k代表间隔，vector中的链表等间隔合并，这样能达到减少一半的目的。+1的目的是针对奇数这种情况，中间一定会剩下一个单独的，这个单独的也要保留在vector中。n代表当前已更新剩下的链表个数，其实也就是存放在lists中的前n个。+1的目的其实也是针对奇数个的情况。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        int n = lists.size();
        while(n > 1){
            int k = (n + 1)/2;
            for(int i = 0;i < n/2;i++)
                lists[i] = merge(lists[i],lists[i + k]);
            n = (n + 1)/2;
        }
        return lists[0];
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                p->next = l1;
                p = p->next;
                l1 = l1->next;
            }
            else{
                p->next = l2;
                p = p->next;
                l2 = l2->next;
            }
        }
        if(l1)
            p->next = l1;
        else
            p->next = l2;
        return dummy->next;
    }
};