【leetcode】合并k个有序链表

合并k个有序链表

问题描述:
合并 k 个排序链表，返回合并后的排序链表.

解法一：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        d={}
        t=[]
        cnt = 0
        head=res=ListNode(0)
        loss_list = []
        while(1): 
            for i in range(len(lists)):
                if lists[i]==None :
                    if not i in loss_list:
                        loss_list.append(i)
                    continue
                d_val = lists[i].val
                if d_val not in d.keys():
                    d[d_val] = []
                d[d_val].append(lists[i])
                t.append(d_val)
                if lists[i].next:
                    lists[i] = lists[i].next
                else:
                    lists[i] = None
                    
            if (len(loss_list) == len(lists)):
                break
        
        for i in sorted(t):
            for n in d[i]:
                res.next = n
                res = res.next
                print(n.val)
        res.next = None
        return head.next

tips：

• 字典一个键值存放多个值可以让value设置为列表类型
  

解法二：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        d={}
        t=[]
        cnt = 0
        head=res=ListNode(0)
        loss_list = []
        while(1): 
            for i in range(len(lists)):
                if lists[i]==None :
                    if not i in loss_list:
                        loss_list.append(i)
                    continue
                d_val = lists[i].val
                t.append(d_val)
                if lists[i].next:
                    lists[i] = lists[i].next
                else:
                    lists[i] = None
                    
            if (len(loss_list) == len(lists)):
                break
        t=sorted(t)
        for i in t:
                res.next=ListNode()
                res = res.next
                res.val=i

        res.next = None
        return head.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 bool cmp(ListNode*a,ListNode* b){
     return a->val<b->val;
 }
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
         vector<ListNode *>node_vec;
         for (int i=0;i<lists.size();i++){
             ListNode* head=lists[i];
             while(head){
                 node_vec.push_back(head);
                 head=head->next;
             }
         }
         if(node_vec.size()==0)
            return NULL;
        std::sort(node_vec.begin(),node_vec.end(),cmp);
        printf("ss");
         for(int i=0;i<node_vec.size()-1;i++){
             node_vec[i]->next=node_vec[i+1];
         }
         node_vec[node_vec.size()-1]->next=NULL;
         return node_vec[0];
    }
};

解法三：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                print(heapq)
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            print("val:{},idx:{}",val,idx)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

tips：

• heapq.heapify(list) 把数组转换为堆
• heapq.heappush(heap,item) 为heap增加元素
• heapq.heappop(heap) 删除堆顶（即最小值）
• heapq.heapreplace(heap, item) 删除最小值并添加新的元素
• heapq.nlargest (n, heap) 查堆中最大的n个数
• heapq.nsmallest(n, heap) #查询堆中的最小元素，n表示查询元素个数

新解法：分而治之

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if  (!l2)
            return l1;
        if  (!l1)
            return l2;
        ListNode st= ListNode(0);
        ListNode *ptr=&st;
        while(l1 && l2){
            if (l1->val<l2->val){
                ptr->next=l1;
                l1=l1->next;
            }
            else{
                ptr->next=l2;
                l2=l2->next;
            }
            ptr = ptr->next;
        }
        if (!l1)
          ptr->next=l2;
        if(!l2)
            ptr->next=l1;
        return st.next;
    }

bool cmp(ListNode*a,ListNode* b){
     return a->val<b->val;
 }
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0)    
            return NULL;
        if(lists.size()==1)
            return lists[0];
        if(lists.size()==2)
            return mergeTwoLists(lists[0],lists[1]);
        int mid=lists.size()/2;
        vector<ListNode*>sub1_lists;
        vector<ListNode*>sub2_lists;
        for (int i=0;i<mid;i++){
            sub1_lists.push_back(lists[i]);
        }
        for (int i=mid;i<lists.size();i++){
            sub2_lists.push_back(lists[i]);
        }
        ListNode* L1=mergeKLists(sub1_lists);
        ListNode* L2=mergeKLists(sub2_lists);
        return mergeTwoLists(L1,L2);
    }
};

如果是两各链表直接对两个链表进行排序；
如果是多个，先一分为二，分别对这两个处理，然后再处理结束后对这两个处理。

递归的妙用
递归比较耗时间和空间