leetcode 23. Merge k Sorted Lists

我会带着你远行 2022-06-09 08:08 138阅读 0赞

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

提议很简单，就是归并排序。

首先想到的即使逐个归并得到最终的结果，但是会超时，这是因为这种会造成数组的size大小不一样，导致归并排序的时间变长；

最好的做法是两两合并，然后在两两合并，这样不会超时，  
需要注意的是**cap=(size+1)/2**，这个是考虑到奇数的情况。

代码如下：

/* class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }*/
    
    public class Solution 
    {
        /*
         * 按照次序两两合并，会超时 
         * */
        public ListNode mergeKLists111(ListNode[] lists)
        {
            ListNode head=new ListNode(-1);
            if(lists.length<=0)
                return head.next;
            if(lists.length==1)
                return lists[0];
    
             //这个循环属于遍历方法
            for(int i=0; i<lists.length;i++)
                head.next=merge(head.next,lists[i]);
            return head.next;   
        }
    
    
        /*
         * 注意分析数组元素数量为0个和1个时候的特殊情况
         * 
         * 很明显可以使用二分方法去做
         * */
        public ListNode mergeKLists(ListNode[] lists)
        {
            ListNode head=new ListNode(-1);
            if(lists.length<=0)
                return head.next;
            if(lists.length==1)
                return lists[0];
    
            int len=lists.length;
            while(len>1)
            {
                int cap=(len+1)/2;
                for(int i=0;i<len/2;i++)
                    lists[i]=merge(lists[i], lists[i+cap]);
                len=cap;
            }
            return lists[0];
        }
    
        private ListNode merge(ListNode listNode, ListNode listNode2) 
        {
            ListNode iter1=listNode;
            ListNode iter2=listNode2;
    
            ListNode head=new ListNode(-1);
            ListNode he=head;
            while(iter1!=null && iter2!=null)
            {
                if(iter1.val<=iter2.val)
                {
                    he.next=new ListNode(iter1.val);
                    he=he.next;
                    iter1=iter1.next;
                }
                else
                {
                    he.next=new ListNode(iter2.val);
                    he=he.next;
                    iter2=iter2.next;
                }
            }
    
            while(iter1!=null)
            {
                he.next=new ListNode(iter1.val);
                he=he.next;
                iter1=iter1.next;
            }
    
            while(iter2!=null)
            {
                he.next=new ListNode(iter2.val);
                he=he.next;
                iter2=iter2.next;
            }
            return head.next;
        }
    }

C++版本的答案如下，这个和CUDA的归并很像，

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    /*
    struct ListNode
    {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) 
        {
            if (lists.size() <= 0)
                return NULL;
    
            if (lists.size() == 1)
                return lists[0];
    
            int len = lists.size();
            while (len > 1)
            {
                int cap = (len + 1) / 2;
                for (int i = 0; i < len/2; i++)
                    lists[i] = mergeTwoLists(lists[i], lists[i + cap]);
                len = cap;
            }
            return lists[0];
        }
    
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
        {
            ListNode* head = new ListNode(-1);
            ListNode* a = head;
            while (l1 != NULL && l2 != NULL)
            {
                if (l1->val < l2->val)
                {
                    a->next = new ListNode(l1->val);
                    l1 = l1->next;
                    a = a->next;
                }
                else
                {
                    a->next = new ListNode(l2->val);
                    l2 = l2->next;
                    a = a->next;
                }
            }
    
            while (l1 != NULL)
            {
                a->next = new ListNode(l1->val);
                l1 = l1->next;
                a = a->next;
            }
    
            while (l2 != NULL)
            {
    
                a->next = new ListNode(l2->val);
                l2 = l2->next;
                a = a->next;
            }
            return head->next;
        }
    };