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(-);

        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 <= )

            return NULL;

        while(n > ){

            int k = (n + )/;

            for(int i = ;i < n/;i++)

                lists[i] = mergeList(lists[i],lists[i + k]);

            n = k;

        }

        return lists[];

    }

    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 > ){

            int k = (n + )/;

            for(int i = ;i < n/;i++)

                lists[i] = merge(lists[i],lists[i + k]);

            n = (n + )/;

        }

        return lists[];

    }

    ListNode* merge(ListNode* l1,ListNode* l2){

        ListNode* dummy = new ListNode(-);

        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;

    }

};

巴特西

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

最新文章

热门文章