23.md

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

解题思路

1. 首先进行归并排序,让两个链表合并成一个有序链表
2. 然后使用递归的方式,如果列表的长度大于2,那么继续进行递归

Python语言版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists) == 0:
            return None
        elif len(lists) == 1:
            return lists[0]
        elif len(lists) == 2:
            return self.mergeTwoLists(lists[0], lists[1])
        mid = int(len(lists) / 2)
        list1 = list()
        for i in range(mid):
            list1.append(lists[i])
        
        list2 = list()
        for i in range(mid, len(lists)):
            list2.append(lists[i])
        l1 = self.mergeKLists(list1)
        l2 = self.mergeKLists(list2)
        return self.mergeTwoLists(l1, l2)


    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        res = h = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                h.next, list1 = list1, list1.next
            else:
                h.next, list2 = list2, list2.next
            h = h.next
        h.next = list1 if list1 else list2
        return res.next

Go语言版本

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoList(list1, list2 *ListNode) *ListNode{
    var res = &ListNode{}
    var pre = res
    for list1 != nil && list2 != nil{
        if list1.Val < list2.Val{
            pre.Next = list1
            list1 = list1.Next
        }else{
            pre.Next = list2
            list2 = list2.Next
        }
        pre = pre.Next
    }
    if list1 != nil {
        pre.Next = list1
    }else{
        pre.Next = list2
    }
    return res.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0{
        return nil
    }else if len(lists) == 1{
        return lists[0]
    }else if len(lists) == 2{
        return mergeTwoList(lists[0], lists[1])
    }
    var mid = int(len(lists)/2)
    var sub1, sub2 []*ListNode
    for i := 0; i < mid; i++ {
        sub1 = append(sub1, lists[i])
    }
    for i:=mid;i<len(lists);i++{
        sub2 = append(sub2, lists[i])
    }

    var l1 *ListNode = mergeKLists(sub1)
    var l2 *ListNode = mergeKLists(sub2)

    return mergeTwoList(l1, l2)
}

C语言版本

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwo(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy -> val = -1;
    struct ListNode* pre = dummy;
    while (list1 != NULL && list2 != NULL){
        if(list1->val < list2->val){
            pre->next = list1;
            list1 = list1->next;
        }else{
            pre->next = list2;
            list2 = list2->next;
        }
        pre = pre->next;
    }
    pre->next = list1 != NULL ? list1 : list2;
    return dummy->next;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if(listsSize == 0){
        return NULL;
    }else if(listsSize == 1){
        return lists[0];
    }else if(listsSize == 2){
        return mergeTwo(lists[0], lists[1]);
    }
    int mid = (int)(listsSize / 2);
    
    struct ListNode* sub1[mid];
    struct ListNode* sub2[listsSize - mid];
    for(int i = 0; i < mid; i++){
        sub1[i] = lists[i];
    }
    
    for(int i = mid; i < listsSize; i++){
        sub2[i-mid] = lists[i];
    }

    int sub1Size = sizeof(sub1)/sizeof(sub1[0]);
    int sub2Size = sizeof(sub2)/sizeof(sub2[0]);
    struct ListNode* l1 = mergeKLists(sub1, sub1Size);
    struct ListNode* l2 = mergeKLists(sub2, sub2Size);

    return mergeTwo(l1, l2);
}