【Day 87 】2022-03-08 - 23.合并 K 个排序链表

[azl397985856]

23.合并 K 个排序链表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/merge-k-sorted-lists/

前置知识

• 堆
• 链表
• 分而治之

  题目描述

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

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

 

示例 1：

输入：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 示例 2：

输入：lists = [] 输出：[] 示例 3：

输入：lists = [[]] 输出：[]  

提示：

k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4

[yetfan]

思路 和day69一道题吧

代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        q = []
        res = ListNode(0)

        for i in lists:
            while i:
                heapq.heappush(q, i.val)
                i = i.next

        temp = res
        while q:
            cur = heapq.heappop(q)
            temp.next = ListNode(cur)
            temp = temp.next

        return res.next

复杂度 时间 O(n) 空间 O(n)

[yinhaoti]

# 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]:
        """
        Topic: LinkedList, Ascending, K lists, Merge
        Idea: 
            1. MergeTwoLists
            2. MergeSort
        TC: O(Klogk * N)   N = # of Node, k = # of lists
        SC: O(logk)
        """
        def mergeTwoLists(l1, l2):
            dummy = ListNode(-1)
            cur = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            if l1:
                cur.next = l1
            if l2:
                cur.next = l2
            return dummy.next

        l = len(lists)
        if l == 0: return
        if l == 1: return lists[0]
        m = l // 2
        l1 = self.mergeKLists(lists[:m])
        l2 = self.mergeKLists(lists[m:])
        return mergeTwoLists(l1, l2)

[zwx0641]

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        ListNode* head;
        if (l1->val < l2->val) {
            head = l1;
            head->next = mergeTwoLists(l1->next, l2);
        } else {
            head = l2;
            head->next = mergeTwoLists(l2->next, l1);
        }
        return head;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0) return nullptr;
        if (n == 1) return lists[0];
        if (n == 2) return mergeTwoLists(lists[0], lists[1]);

        int m = n / 2;
        vector<ListNode*> first;
        vector<ListNode*> second;
        for (int i = 0; i < m; i++) {
            first.push_back(lists[i]);
        }
        for (int i = m; i < n; i++) {
            second.push_back(lists[i]);
        }
        return mergeTwoLists(mergeKLists(first), mergeKLists(second));
    }
};

[rzhao010]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) return lists[start];

        if (start > end) return null;

        int mid = start + (end - start) / 2;
        return mergeTwoList(merge(lists, start, mid), merge(lists, mid + 1, end));
    }

    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoList(l1,  l2.next);
            return l2;
        }
    }
}

[Yrtryannn]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                cur.next = aPtr;
                aPtr = aPtr.next;
            } else {
                cur.next = bPtr;
                bPtr = bPtr.next;
            }
            cur = cur.next;
        }
        cur.next = (aPtr != null ? aPtr : bPtr);
        return dummy.next;
    }
}

[zhiyuanpeng]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists or not any([h for h in lists]):
            return None
        # initialize a head and pointer
        head = p = ListNode(0)
        q = [(node.val, i, node) for i, node in enumerate(lists) if node]
        index = len(q)
        heapq.heapify(q)
        while len(q):
            _, _, n = heapq.heappop(q)
            p.next = n
            n = n.next
            if n:
                index += 1
                heapq.heappush(q, (n.val, index, n))
            p = p.next
        return head.next

[ZacheryCao]

Idea:

Divide and Conqur

Code:

# 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 not lists:
            return None
        n = len(lists)
        i = 1
        while i<n:
            for k in range(0, n, i*2):
                if k+i<n:
                    lists[k] = self.merge2Lists(lists[k], lists[k+i])
            i *= 2
        return lists[0]

    def merge2Lists(self, l1,l2):
        dummy=ListNode(0)
        head=dummy 
        while l1 and l2:
            if l1.val<l2.val:
                head.next = ListNode(l1.val)
                l1= l1.next
            else:
                head.next = ListNode(l2.val)
                l2= l2.next
            head = head.next
        while l1:
            head.next = ListNode(l1.val)
            l1= l1.next
            head = head.next
        while l2:
            head.next = ListNode(l2.val)
            l2= l2.next
            head = head.next
        return dummy.next

Complexity:

TIme: O(N logk), N total nodes. k: total lists Space: O(1)

[QinhaoChang]

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: import heapq minheap = []

    dummy = ListNode(-1)
    head = dummy
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(minheap, (lists[i].val, i))

    while minheap:
        value, index = heapq.heappop(minheap)
        head.next = ListNode(value)
        head = head.next

        lists[index] = lists[index].next
        if lists[index]:
            heapq.heappush(minheap, (lists[index].val, index))
    return dummy.next

[cszys888]

# 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]:
        import heapq
        k = len(lists)
        if k == 0:
            return None
        heap = []
        for i in range(k):
            if lists[i]:
                heap.append((lists[i].val, i))
        heapq.heapify(heap)

        dummy = ListNode()
        cur = dummy
        while heap:
            value, index = heapq.heappop(heap)
            if lists[index].next:
                lists[index] = lists[index].next
                heapq.heappush(heap, (lists[index].val, index))
            cur.next = ListNode(value)
            cur = cur.next
        return dummy.next

time complexity: O(kn*logk) space complexity: O(k)

[yan0327]

type hp []*ListNode
func(h hp) Len() int {return len(h)}
func(h hp) Less(i,j int) bool {return h[i].Val < h[j].Val}
func(h hp) Swap(i,j int){h[i],h[j] = h[j],h[i]}
func(h *hp) Push(x interface{}) {*h = append(*h,x.(*ListNode))}
func(h *hp) Pop() interface{}{
    out := *h
    x := out[len(out)-1]
    *h = out[:len(out)-1]
    return x
}
func mergeKLists(lists []*ListNode) *ListNode {
   dummy := &ListNode{}
   cur := dummy
   h := &hp{}
   heap.Init(h)
   for _,list := range lists{
       if list != nil{
           heap.Push(h,list)
       }
   }
   for h.Len() != 0{
       node := heap.Pop(h).(*ListNode)
       cur.Next = node
       cur = cur.Next
       node = node.Next
       if node != nil{
           heap.Push(h,node)
       }
   }
   return dummy.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    n := len(lists)
    if n == 0{
        return nil
    }
    if n == 1{
        return lists[0]
    }
    mid := n>>1
    return merge(mergeKLists(lists[:mid]),mergeKLists(lists[mid:]))
}

func merge(l1 *ListNode,l2 *ListNode) *ListNode{
    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil{
        if l1.Val < l2.Val{
            cur.Next = l1
            l1 = l1.Next
        }else{
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil{
        cur.Next = l1
    }
    if l2 != nil{
        cur.Next = l2
    }
    return dummy.Next
}

[Tesla-1i]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        q = []
        res = ListNode(0)

        for i in lists:
            while i:
                heapq.heappush(q, i.val)
                i = i.next

        temp = res
        while q:
            cur = heapq.heappop(q)
            temp.next = ListNode(cur)
            temp = temp.next

        return res.next

[1149004121]

23. 合并K个升序链表

思路

最大堆。

代码

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    let len = lists.length;
    if(len == 1) return lists[0];
    if(len == 0) return null; 
    let mid = len >> 1;
    let p1 = mergeKLists(lists.slice(0, mid));
    let p2 = mergeKLists(lists.slice(mid, len));
    let dummy = new ListNode(0);
    let cur = dummy;
    while(p1 && p2){
        if(p1.val <= p2.val){
            cur.next = p1;
            p1 = p1.next;
        }else{
            cur.next = p2;
            p2 = p2.next;
        };
        cur = cur.next;
    };
    if(p1) cur.next = p1;
    if(p2) cur.next = p2;
    return dummy.next;
};

复杂度分析

• 时间复杂度：O( NlogN LEN ) 。
• 空间复杂度：O(N * logN) 。

[xuhzyy]

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if len(lists) == 0:
            return None

        if len(lists) == 1:
            return lists[0]

        mid = len(lists) // 2
        lists1 = lists[:mid]
        lists2 = lists[mid:]
        return self.mergeTwoLists(self.mergeKLists(lists1), self.mergeKLists(lists2))

    def mergeTwoLists(self, list1, list2):
        dummyhead = ListNode()
        pre = dummyhead
        while(list1 and list2):
            if list1.val > list2.val:
                pre.next = list2
                list2 = list2.next
            else:
                pre.next = list1
                list1 = list1.next
            pre = pre.next
        pre.next = list1 if list1 else list2
        return dummyhead.next

[Myleswork]

思路

就是常规的排序，无非就是这个是链表，还有K个

代码

class Solution {
private:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode head(0), *tail = &head;
        while (a && b) {
            if (a->val < b->val) { tail->next = a; a = a->next; }
            else { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return head.next;
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return NULL;
        for (int N = lists.size(); N > 1; N = (N + 1) / 2) {
            for (int i = 0; i < N / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[N - 1 - i]);
            }
        }
        return lists[0];
    }
};

[AIBotao]

class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); }

private ListNode merge(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];

    if (start > end) return null;

    int mid = start + (end - start) / 2;
    return mergeTwoList(merge(lists, start, mid), merge(lists, mid + 1, end));
}

private ListNode mergeTwoList(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoList(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoList(l1,  l2.next);
        return l2;
    }
}

}

[xinhaoyi]

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode() {}
• ListNode(int val) { this.val = val; }
• ListNode(int val, ListNode next) { this.val = val; this.next = next; }
• } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) //特判 return null; //优先队列，按照值从小到大排序 PriorityQueue queue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val); //排序后的链表的头节点 ListNode newHead = new ListNode(-1); ListNode l1 = newHead; //将链表数组中每个链表加入队列中
  for (ListNode i : lists)
  if (i != null) queue.add(i); while (!queue.isEmpty()) { //将链表数组中最小的值的那整个链表弹出
  l1.next = queue.poll(); //遍历下一个节点 l1 = l1.next; //如果该链表不为空
  if (l1.next != null) //将该链表下一个值加入队列
  queue.add(l1.next); } return newHead.next; } }

[Toms-BigData]

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0{
        return nil
    }
    var list []int
    for i := 0; i < len(lists); i++ {
        head:=lists[i]
        for head!=nil{
            list = append(list, head.Val)
            head = head.Next
        }
    }
    if len(list) == 0{
        return nil
    }
    sort.Slice(list, func(i, j int) bool { return list[i]<list[j]})
    var head ListNode
    head.Val = list[0]
    point:=&head
    for i := 1; i < len(list); i++ {
        node:=ListNode{Val: list[i]}
        point.Next = &node
        point = point.Next
    }
    return &head
}

[yijing-wu]

// 分治法 Divide And Conquer - 链表两两合并 + 迭代
// K 条链表的总结点数是 N，平均每条链表有 N/K 个节点，合并两条链表的时间复杂度是 O(N/K)
// 从 K 条链表开始两两合并成 1 条链表，因此每条链表都会被合并 logK 次，因此 K 条链表会被合并 K∗logK 次，因此总共的时间复杂度是 K*logK*N/K 即 O（NlogK)
// 时间复杂度：O(NlogK), SC = O(1)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // special cases
        if(lists.length < 1) return null;

        int k = lists.length;   // k 为 number of lists that need to be merged
        while(k > 1) {
            int idx = 0;
            for(int i = 0; i < k; i += 2) {
                if(i == k - 1) {
                    // 如果需要merged的list数量为odd，直接存入
                    lists[idx++] = lists[i];
                } else {
                    // merged
                    lists[idx++] = merge2Lists(lists[i], lists[i+1]);
                }
            }
            k = idx;    // update k
        }
        return lists[0];
    }

    private ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = l1 == null? l2: l1;
        return dummyHead.next;
    }
}

[luhnn120]

思路

分治

代码

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists.length) {
    return null;
  }
  const merge = (head1, head2) => {
    let dummy = new ListNode(0);
    let cur = dummy;
    while (head1 && head2) {
      if (head1.val < head2.val) {
        cur.next = head1;
        head1 = head1.next;
      } else {
        cur.next = head2;
        head2 = head2.next;
      }
      cur = cur.next;
    }
    cur.next = head1 == null ? head2 : head1;
    return dummy.next;
  };
  const mergeLists = (lists, start, end) => {
    if (start + 1 == end) {
      return lists[start];
    }
    let mid = (start + end) >> 1;
    let head1 = mergeLists(lists, start, mid);
    let head2 = mergeLists(lists, mid, end);
    return merge(head1, head2);
  };
  return mergeLists(lists, 0, lists.length);
};

复杂度

时间复杂度 O(kn×logk) 空间复杂度 O(logk)

[LannyX]

思路

PQ

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        ListNode dummy = new ListNode();
        ListNode p = dummy;

        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b) -> (a.val - b.val)
        );

        for(ListNode head :lists){
            if(head != null){
                pq.add(head);
            }
        }
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
            p = p.next;
        }
        return dummy.next;
    }
}

[zuiaiqun]

func mergeKLists(lists []*ListNode) *ListNode {
    total := len(lists)
    if total == 0 {
        return nil
    }
    if total == 1 {
        return lists[0]
    }
    l1 := mergeKLists(lists[:total/2])
    l2 := mergeKLists(lists[total/2:])

    head := &ListNode{}
    tail := head

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            tail = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            tail = l2
            l2 = l2.Next
        }
    }
    if l1 == nil {
        tail.Next = l2
    }
    if l2 == nil {
        tail.Next = l1
    }
    return head.Next

}

[zhangzz2015]

思路

• 利用heap 实现k路合并排序。把所有的list vec 的头指针放入heap。每次从heap取出最小的，并把下一个放入堆。时间复杂度为O(n * logk)，n为所有的节点。空间复杂度为 O(k)

关键点

代码

• 语言支持：C++

C++ Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        /// heap. 
        auto comp = [](ListNode * &  node1, ListNode * & node2)
        {
            return node1->val > node2->val; 

        }; 
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp) > pq(comp); 
        for(auto& it: lists)
        {
            if(it!=NULL)
                pq.push(it); 
        }
        ListNode tmp; 
        ListNode* prev = &tmp; 
        while(pq.size())
        {
            auto topNode= pq.top(); 
            pq.pop(); 
            prev->next = topNode; 
            prev = topNode; 
            if(topNode->next)
                pq.push(topNode->next);             
        }

        return tmp.next;                 
    }
};

[haixiaolu]

思路

结合 21.合并链表

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # edge cases
        if not lists or len(lists) == 0:
            return None

        # take pair of list and merge them until there is one list left
        while len(lists) > 1:  # keep reducing it
            mergedLists = []

            for i in range(0, len(lists), 2): # want want to take pairs, increment 2
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None # it might outbound, that's why need to check it
                mergedLists.append(self.mergeList(l1, l2))
            # one list left
            lists = mergedLists
        return lists[0]

    def mergeList(self, l1, l2):
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next

        if l1:
            tail.next = l1
        if l2:
            tail.next = l2
        return dummy.next 

• Time: O(n)
• Space: O(n)

[Moin-Jer]

class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); }

public ListNode merge(ListNode[] lists, int l, int r) {
    if (l == r) {
        return lists[l];
    }
    if (l > r) {
        return null;
    }
    int mid = (l + r) >> 1;
    return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}

public ListNode mergeTwoLists(ListNode a, ListNode b) {
    if (a == null || b == null) {
        return a != null ? a : b;
    }
    ListNode head = new ListNode(0);
    ListNode tail = head, aPtr = a, bPtr = b;
    while (aPtr != null && bPtr != null) {
        if (aPtr.val < bPtr.val) {
            tail.next = aPtr;
            aPtr = aPtr.next;
        } else {
            tail.next = bPtr;
            bPtr = bPtr.next;
        }
        tail = tail.next;
    }
    tail.next = (aPtr != null ? aPtr : bPtr);
    return head.next;
}

}

[Alexno1no2]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for i in lists:
            while i:
                heapq.heappush(heap,i.val)
                i = i.next

        head = c = ListNode(-1)
        while heap:
            c.next = ListNode(heapq.heappop(heap))
            c = c.next
        return head.next

[biaohuazhou]

class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); }

private ListNode merge(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];

    if (start > end) return null;

    int mid = start + (end - start) / 2;
    return mergeTwoList(merge(lists, start, mid), merge(lists, mid + 1, end));
}

private ListNode mergeTwoList(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoList(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoList(l1,  l2.next);
        return l2;
    }
}

}

[ZJP1483469269]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergetwo(l1 , l2):
            if not l1:
                return l2
            if not l2:
                return l1

            if l1.val < l2.val:
                l1.next = mergetwo(l1.next, l2)
                return l1
            else:
                l2.next = mergetwo(l1, l2.next)
                return l2

        def merge(ls , i ,j):
            if i == j:
                return ls[i]
            mid = (i +  j)>> 1
            l1 = merge(ls , i , mid)
            l2 = merge(ls ,mid + 1 , j)
            return mergetwo(l1,l2)
        n = len(lists)
        if n == 0:
            return None
        else:
            return merge(lists , 0 ,n-1)

[spacker-343]

思路

归并

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0) {
            return null;
        }
        return mergeKListsHelper(lists, 0, len - 1);
    }

    private ListNode mergeKListsHelper(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = (left + right) / 2;
        ListNode leftNode = mergeKListsHelper(lists, left, mid);
        ListNode rightNode = mergeKListsHelper(lists, mid + 1, right);
        return mergeTwo(leftNode, rightNode);
    }

    private ListNode mergeTwo(ListNode left, ListNode right) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                p.next = left;
                p = p.next;
                left = left.next;
            } else {
                p.next = right;
                p = p.next;
                right = right.next;
            }
        }
        if (right != null) {
            p.next = right;
        }
        if (left != null) {
            p.next = left;
        }
        return dummy.next;
    }
}

[hdyhdy]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    k := len(lists)
    if k == 0{
        return nil
    }else if k == 1 {
        return lists[0]
    }else {
        mid := k / 2 
        return merge(mergeKLists(lists[:mid]),mergeKLists(lists[mid:]))
    }
}

func merge(l1 *ListNode, l2 *ListNode) *ListNode{
    dummy := new(ListNode)
    ans := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            ans.Next = l1
            l1 = l1.Next
        }else {
            ans.Next = l2
            l2 = l2.Next
        }
        ans = ans.Next
    }
    if l1 != nil {
        ans.Next = l1
    } 
    if l2 != nil {
        ans.Next = l2 
    }
    return dummy.Next
}

[ACcentuaLtor]

遍历，转化为之前做过的两个有序链表合并的题目 class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists:return None res = None for list_i in lists: res = self.mergeTwoLists(res,list_i) return res

def mergeTwoLists(self,l1:ListNode,l2:ListNode):
    dummy = ListNode(-1)
    du = dummy
    while l1 and l2:
        if l1.val < l2.val:
            du.next = l1
            l1 = l1.next
        else:
            du.next = l2
            l2 = l2.next
        du = du.next
    if not l1:du.next = l2
    else:du.next = l1
    return dummy.next

[moirobinzhang]

Code:

public class Solution {

public SortedDictionary<int, Queue<ListNode>> sortedNodes;

public ListNode MergeKLists(ListNode[] lists) {
    sortedNodes = new SortedDictionary<int, Queue<ListNode>>();

    foreach(var node in lists)
    {
        if (node != null)
            AddNodes(node);
    }
    ListNode dummyNode = new ListNode(0);
    ListNode cursorNode = dummyNode;

    while (sortedNodes.Count > 0)
    {
        ListNode minNode = GetMiniNode();
        if (minNode.next != null)
             AddNodes(minNode.next);

        cursorNode.next = minNode;
        cursorNode =  cursorNode.next;
    }        

    return dummyNode.next; 
}

public void AddNodes(ListNode listNode)
{
    if (!sortedNodes.ContainsKey(listNode.val))
        sortedNodes.Add(listNode.val, new Queue<ListNode>());

    sortedNodes[listNode.val].Enqueue(listNode);
}

public ListNode GetMiniNode()
{
    if (sortedNodes == null || sortedNodes.Count <= 0)
        return null;

    int minKey = sortedNodes.First().Key;
    ListNode minNode = sortedNodes[minKey].Dequeue();
    if (sortedNodes[minKey].Count == 0)
        sortedNodes.Remove(minKey);

    return minNode;        
}

}

[shamworld]

var mergeKLists = function(lists) {
    const len = lists.length;
    if(!len) return null;
    if(len == 1) return lists[0];
    let  arr = new Array();
    for(let i = 0; i < len; i++){
        let temp = lists[i];
        while(temp){
            arr.push(temp.val);
            temp = temp.next;
        }
    }
    arr.sort((a,b)=>a-b);
    let res = new ListNode();
    let cur = res;
    for(let i = 0; i < arr.length; i++){
        let node = new ListNode(arr[i]);
        cur.next = node;
        cur = cur.next;
    }
    return res.next;
};

[tbw19970424]

思路

关键点

• 每次在k个head里挑出最小的，可以考虑用小顶堆作为工具以logk的时间费用实现

代码

• 语言支持：Python3

Python3 Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(0)
        pit = dummy
        pq = [] # 小顶堆
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(pq, (lists[i].val, i))
        while pq:
            val, idx = heapq.heappop(pq)
            pit.next = ListNode(val)
            pit = pit.next
            lists[idx] = lists[idx].next
            if lists[idx]:
                heapq.heappush(pq, (lists[idx].val, idx))
        return dummy.next

复杂度分析

令 n 为每个链表的平均长度，k为需要合并的链表数。

• 时间复杂度：$O(nlogk)$
• 空间复杂度：$O(k)$

[callmeerika]

思路

分治

代码

var merge = (a, b) => {
    if(!a || !b) return a ? a : b;
    let head = new ListNode(null);
    let tail = head;
    while (a && b) {
        if (a.val < b.val) {
            tail.next = a; 
            a = a.next;
        } else {
            tail.next = b; 
            b = b.next;
        }
        tail = tail.next;
    }
    tail.next = a ? a : b;
    return head.next;
}
var mergeTwo = (list, left, right) => {
    if (left === right) return list[left];
    if (left > right) return null;
    let  mid = (left + right) >> 1;
    return merge(mergeTwo(list, left, mid), mergeTwo(list, mid + 1, right));
}
var mergeKLists = function(lists) {
    return mergeTwo(lists, 0, lists.length - 1);
};

复杂度

时间复杂度：O(knlogk)
空间复杂度：O(logk)

[alongchong]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}

[dahaiyidi]

Problem

[23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists/)

++

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

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

---

Note

• 分治。

---

Complexity

• 时间O：kn*logk
• 空间O：logk

---

Python

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b){
        if ((!a) || (!b)) return a ? a : b;
        ListNode dummy, *p = &dummy;
        ListNode* p1 = a;
        ListNode* p2 = b;
        // ListNode* p = &dummy;
        while(p1 && p2){
            if(p1->val <= p2->val){
                p->next = p1;
                p1 = p1->next;
                p = p->next;
            }
            else if(p1->val > p2->val){
                p->next = p2;
                p2 = p2->next;
                p = p->next;
            }
        }
        if(p1){
            p->next = p1;
        }
        else if(p2){
            p->next = p2;
        }

        return dummy.next;
    }

    ListNode* merge(vector<ListNode*>& lists, int left, int right){
        if(left == right){
            return lists[left];
        }
        if(left > right){
            return nullptr;
        }

        int mid = left + ((right - left) >> 1);
        ListNode* a = merge(lists, left, mid);
        ListNode* b = merge(lists, mid + 1, right);
        return mergeTwoLists(a, b);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

From : https://github.com/dahaiyidi/awsome-leetcode

[tian-pengfei]

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        ListNode* baseList = nullptr;
        ListNode* basePos = nullptr;
        bool loopCondition = true;
        while(loopCondition){
            loopCondition= false;
            int min_index = -1;
            int min_value = 10001;
            for(int i=0 ;i<lists.size();i++){
                if(lists[i]!= nullptr){
                    loopCondition = true;
                    if(min_value>lists[i]->val){
                        min_value = lists[i]->val;
                        min_index = i;
                    }
                }
            }
            if(loopCondition){
                if(basePos== nullptr){
                     baseList = basePos = lists[min_index];
                }else{
                    basePos->next = lists[min_index];
                    basePos =  basePos->next;
                }
                lists[min_index] =  lists[min_index]->next;
                basePos->next = nullptr;
            }

        }
        return baseList;

    }
};

[pwqgithub-cqu]

class Solution { public: ListNode mergeKLists(vector<ListNode>& lists) { /// heap. auto comp = [](ListNode & node1, ListNode & node2) { return node1->val > node2->val;

    }; 
    priority_queue<ListNode*, vector<ListNode*>, decltype(comp) > pq(comp); 
    for(auto& it: lists)
    {
        if(it!=NULL)
            pq.push(it); 
    }
    ListNode tmp; 
    ListNode* prev = &tmp; 
    while(pq.size())
    {
        auto topNode= pq.top(); 
        pq.pop(); 
        prev->next = topNode; 
        prev = topNode; 
        if(topNode->next)
            pq.push(topNode->next);             
    }

    return tmp.next;                 
}

};

[guangsizhongbin]

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode() {}
• ListNode(int val) { this.val = val; }
• ListNode(int val, ListNode next) { this.val = val; this.next = next; }

• } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { return merge(lists, 0, lists.length - 1); }

  public ListNode merge(ListNode[] lists, int l, int r){ if (l == r){ return lists[l]; } if (l > r){ return null; } int mid = (l + r) >> 1; return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); }

  public ListNode mergeTwoLists(ListNode a, ListNode b){ if (a == null || b == null){ return a != null ? a : b; } ListNode head = new ListNode(0); ListNode tail = head, aPtr = a, bPtr = b; while (aPtr != null && bPtr != null){ if (aPtr.val < bPtr.val){ tail.next = aPtr; aPtr = aPtr.next; } else { tail.next = bPtr; bPtr = bPtr.next; } tail = tail.next; } tail.next = (aPtr != null ? aPtr : bPtr); return head.next; } }

[xjhcassy]

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode fakeHead = new ListNode(0);
        ListNode temp = fakeHead;

        for (ListNode head: lists)
            if (head != null)
                queue.offer(head);

        while (!queue.isEmpty()) {

            ListNode curr = queue.poll();

            if (curr.next != null)
                queue.offer(curr.next);

            temp.next = curr;
            temp = temp.next;
        }
        return fakeHead.next;
    }
}

[GaoMinghao]

思路

堆

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = new ListNode();
        ListNode flag = ans;
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode list : lists) {
            if (list != null)
                heap.add(list);
        }
        while(!heap.isEmpty()) {
            ListNode current = heap.poll();
            ans.next = new ListNode(current.val);
            ans = ans.next;
            if(current.next!=null) {
                heap.add(current.next);
            }
        }
        return flag.next;
    }
}

时间复杂度

O(NlogN)

[Hacker90]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

    PriorityQueue<ListNode> queue = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
    ListNode fakeHead = new ListNode(0);
    ListNode temp = fakeHead;

    for (ListNode head: lists)
        if (head != null)
            queue.offer(head);

    while (!queue.isEmpty()) {

        ListNode curr = queue.poll();

        if (curr.next != null)
            queue.offer(curr.next);

        temp.next = curr;
        temp = temp.next;
    }
    return fakeHead.next;
}

}

[for123s]

class Solution {
public:

    ListNode* merge2Lists(ListNode* l, ListNode* r)
    {
        if(!l)
            return r;
        if(!r)
            return l;
        ListNode* idx = new ListNode();
        ListNode* head = idx;
        while(l&&r)
        {
            if(l->val<r->val)
            {
                idx->next = l;
                l = l->next;
            }
            else
            {
                idx->next = r;
                r = r->next;
            }
            idx = idx->next;
            idx->next = nullptr;
        }
        while(l)
        {
            idx->next = l;
            l = l->next;
            idx = idx->next;
            idx->next = nullptr;
        }
        while(r)
        {
            idx->next = r;
            r = r->next;
            idx = idx->next;
            idx->next = nullptr;
        }
        return head->next;
    }

    ListNode* merge(vector<ListNode*>& lists,int l,int r)
    {
        if(l==r)
            return lists[l];
        if(l>r)
            return nullptr;
        int mid = (l+r)>>1;
        return merge2Lists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists,0,lists.size()-1);
    }
};

[ChenJingjing85]

# 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[ListNode]) -> ListNode:
        def mergeTwoLists(root1, root2):
            n1 = root1
            n2 = root2
            tempHead = ListNode(0)
            head = tempHead
            while (n1 != None and n2 != None):
                if n1.val < n2.val:
                    tempHead.next = n1
                    n1 = n1.next
                else:
                    tempHead.next = n2
                    n2 = n2.next
                tempHead = tempHead.next
            tempHead.next = n1 if n2 == None else n2
            return head.next

        if not lists:
             return None
        if len(lists) <= 1:
            return lists[0]       
        merged = mergeTwoLists(lists[0], lists[1])
        for i in range(2, len(lists)):
            merged = mergeTwoLists(merged, lists[i])
        return merged

[fornobugworld]

原地修改版

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))
        while head:
            val, idx = heapq.heappop(head)
            p.next = lists[idx]
            p = p.next
            if lists[idx].next:
                lists[idx] = lists[idx].next
                heapq.heappush(head, (lists[idx].val, idx))                
        return dummy.next

[charlestang]

思路

归并排序

将所有的链表，两个一组，进行合并。

时间复杂度 O(k n log n)

k 是链表的平均长度。n 是链表的数量。

代码

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
            if not head1 and not head2: return None
            if not head1: return head2
            if not head2: return head1

            dummy = ListNode()            
            p = dummy
            while head1 and head2:
                if head1.val < head2.val:
                    p.next = head1
                    head1 = head1.next
                else:
                    p.next = head2
                    head2 = head2.next
                p = p.next
            if head1:
                p.next = head1
            if head2:
                p.next = head2
            return dummy.next

        def _mergeKLists(l: int, r: int) -> Optional[ListNode]:
            if l == r: return lists[l]
            m = (l + r) >> 1
            head1 = _mergeKLists(l, m)
            head2 = _mergeKLists(m + 1, r)
            return merge(head1, head2)

        n = len(lists)
        return _mergeKLists(0, n - 1) if n > 0 else None

[hx-code]

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: def merge(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]: if not head1 and not head2: return None if not head1: return head2 if not head2: return head1

        dummy = ListNode()            
        p = dummy
        while head1 and head2:
            if head1.val < head2.val:
                p.next = head1
                head1 = head1.next
            else:
                p.next = head2
                head2 = head2.next
            p = p.next
        if head1:
            p.next = head1
        if head2:
            p.next = head2
        return dummy.next

    def _mergeKLists(l: int, r: int) -> Optional[ListNode]:
        if l == r: return lists[l]
        m = (l + r) >> 1
        head1 = _mergeKLists(l, m)
        head2 = _mergeKLists(m + 1, r)
        return merge(head1, head2)

    n = len(lists)
    return _mergeKLists(0, n - 1) if n > 0 else None

[577961141]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //特判
        if(lists==null||lists.length==0)return null;

        //开始遍历进行合并
        //合并的方法是  lists[j],lists[j+i]  

        //0 1 2 3 4 5
        //0   2   4
        //0       4
        //0

        //0 1 - 2 3 -4 5 
        //i=1  j=0 2 4 j=j+i*2
        //0 2  4
        //i=2 j=0 4 j=j+i*2
        for(int i=1;i<lists.length;i*=2){
            for(int j=0;j+i<lists.length;j=j+i*2){
                lists[j] = mergeTwoSort(lists[j],lists[j+i]);
            }
        }
        return lists[0];
    }
    //定义合并两条链表的函数  采取拼接的方法
    ListNode mergeTwoSort(ListNode l1,ListNode l2){
        if(l1==null)return l2;//如果l1为空 返回l2
        if(l2==null)return l1;//反之返回l1
        if(l1.val<l2.val){//如果当前的l1的值小于l2则嫁接到l1上
            l1.next = mergeTwoSort(l1.next,l2);
            return l1;
        }else{//反之嫁接到l2上
            l2.next = mergeTwoSort(l2.next,l1);
            return l2;
        }
    }
}

[machuangmr]

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
     if(lists.length == 0) {
         return null;
     }
     return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge (ListNode[] lists, int lo, int high) {
        if(lo == high) {
            return lists[lo];
        }

        int mid = lo + (high - lo) / 2;
        ListNode l1 = merge(lists, lo, mid);
        ListNode l2 = merge(lists, mid + 1, high);
        return merge2Lists(l1, l2);
    }

    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }

        ListNode newList = null;
        if(l1.val < l2.val){
            newList = l1;
            newList.next = merge2Lists(l1.next, l2);
        } else {
            newList = l2;
            newList.next = merge2Lists(l1, l2.next);
        }
        return newList;
    }
}

[taojin1992]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));

        for (ListNode list : lists) {
            if (list != null) {
                minHeap.offer(list);
            }
        }

        ListNode dummy = new ListNode(0, null), cur = dummy;
        while (!minHeap.isEmpty()) {
            ListNode curMin = minHeap.poll();
            cur.next = curMin;
            cur = cur.next;
            if (curMin.next != null) {
                minHeap.offer(curMin.next);
            }
        }
        return dummy.next;
    }
    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null; // important
        if (lists.length == 1) return lists[0];
        if (lists.length == 2) return merge(lists[0], lists[1]);

        int mid = lists.length >> 1;
        ListNode[] l1 = new ListNode[mid];
        for (int i = 0; i < mid; i++) {
            l1[i] = lists[i];
        }

        ListNode[] l2 = new ListNode[lists.length - mid];
        for (int i = mid; i < lists.length; i++) {
            l2[i - mid] = lists[i];
        }

        return merge(mergeKLists(l1),mergeKLists(l2));
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode dummy = new ListNode(0);
        ListNode cur1 = l1, cur2 = l2, cur = dummy;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if (cur1 != null) {
             cur.next = cur1;
        }
        if (cur2 != null) {
             cur.next = cur2;
        }
        return dummy.next;
    }
}