【Day 69 】2023-04-23 - 23. 合并 K 个排序链表

[azl397985856]

23. 合并 K 个排序链表

入选理由

暂无

题目地址

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

前置知识

• 链表
• 归并排序

  题目描述

合并  k  个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [   1->4->5,   1->3->4,   2->6 ] 输出: 1->1->2->3->4->4->5->6

[aswrise]

class Solution:
    def mergeKLists(self, lists):
        import heapq
        dummy = ListNode(0)
        p = dummy
        heads = []
        for idx, node in enumerate(lists):
            if node:
                heapq.heappush(heads, (node.val, idx))
                lists[idx] = lists[idx].next

        while heads:
            val, idx = heapq.heappop(heads)
            node = ListNode(val)
            p.next = node
            p = p.next
            if lists[idx]:
                node = lists[idx]
                heapq.heappush(heads, (node.val, idx))
                lists[idx] = lists[idx].next

        return dummy.next

[RestlessBreeze]

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* merge(ListNode* A, ListNode* B)
    {
        ListNode* temp = new ListNode(0);
        ListNode* newHead = temp;
        while (A && B)
        {
            if (A->val < B->val)
            {
                temp->next = A;
                A = A->next;
                temp = temp->next;
            }
            else
            {
                temp->next = B;
                B = B->next;
                temp = temp->next;
            }
        }
        while (A)
        {
            temp->next = A;
            A = A->next;
            temp = temp->next;
        }
        while (B)
        {
            temp->next = B;
            B = B->next;
            temp = temp->next;
        }
        return newHead->next;
    }

    ListNode* Merge(vector<ListNode*>& lists, int left, int right)
    {
        if (left == right)
            return lists[left];
        int mid = left + (right - left) / 2;
        return merge(Merge(lists, left, mid), Merge(lists, mid + 1, right));
    }

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

[Meisgithub]

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        return mergeSort(lists, 0, n - 1);
    }

    ListNode*  merge(ListNode* list1, ListNode* list2)
    {
        ListNode* dummy = new ListNode();
        ListNode* p = dummy;
        ListNode* p1 = list1;
        ListNode* p2 = list2;
        while (p1 && p2)
        {
            if (p1->val <= p2->val)
            {
                p->next = p1;
                p1 = p1->next;
            }
            else
            {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        p->next = p1 == nullptr ? p2 : p1;
        return dummy->next;
    }

    ListNode* mergeSort(vector<ListNode*>& lists, int left, int right)
    {
        if (left > right)
        {
            return nullptr;
        }
        if (left == right)
        {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode* leftNode = mergeSort(lists, left, mid);
        ListNode* rightNode = mergeSort(lists, mid + 1, right);
        ListNode* ret = merge(leftNode, rightNode);
        return ret;
    }
};

[Diana21170648]

思路

分治，归并排序，链表

class Solution:
        def  mergeKLists(self, lists: List[ListNode]) -> ListNode:
               n = len(lists)

              # basic cases
             if lenth == 0:
                    return None
            if lenth == 1:
                  return lists[0]
            if lenth == 2:
                 return self.mergeTwoLists(lists[0], lists[1])

         # divide and conqure if not basic cases
                  mid = n // 2
                     return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))

       def  mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
              res = ListNode(0)
             c1, c2, c3 = l1, l2, res
             while c1or c2:
                if c1and c2:
                if c1.val < c2.val:
                    c3.next = ListNode(c1.val)
                    c1 = c1.next
               else:
                    c3.next = ListNode(c2.val)
                    c2 = c2.next
                   c3 = c3.next
             elif c1:
                c3.next = c1
                break
            else:
                c3.next = c2
               break

          return res.next

**复杂度分析**
- 时间复杂度：O(kn*logk)，其中 N 为数组长度。
- 空间复杂度：O(logk)

[airwalkers]

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

        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);

        for (ListNode head: lists) {
            if (head != null) {
                pq.add(head);
            }

        }

        ListNode pre = new ListNode();
        ListNode p = pre;

        while (!pq.isEmpty()) {
            ListNode poll = pq.poll();
            if (poll.next != null) {
                pq.add(poll.next);
            }
            p.next = poll;
            p = p.next;
            poll.next = null;
        }

        return pre.next;
    }
}

[FireHaoSky]

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

思路：分治，归并

代码：python

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        return self.merge(lists, 0, len(lists)-1)

    def merge(self, lists, left, right):
        if left == right:
            return lists[left]

        if left > right:
            return None

        mid = left + (right - left)//2
        return self.mergeTwoLists(self.merge(lists, left, mid), self.merge(lists, mid+1, right))

    def mergeTwoLists(self, a, b):
        if not a or not b:
            return a if a else b
        head = ListNode(0)
        tail = head
        aPtr = a
        bPtr = b
        while aPtr and bPtr:
            if aPtr.val < bPtr.val:
                tail.next = aPtr
                aPtr = aPtr.next
            else:
                tail.next = bPtr
                bPtr = bPtr.next
            tail = tail.next

        tail.next = aPtr if aPtr else bPtr
        return head.next

复杂度分析：

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

[kofzhang]

思路

归并排序

复杂度

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

代码

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:        
        def devide(ls):
            if not ls:
                return None
            n = len(ls)
            if n == 1:
                return ls[0]
            half = n // 2
            return merge(devide(ls[:half]), devide(ls[half:]))

        def merge(l1, l2):
            if not l1:
                return l2
            if not l2:
                return l1
            d = ListNode(-1)
            cur = d
            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 not l1:
                cur.next = l2                
            elif not l2:
                cur.next = l1

            return d.next

        return devide(lists)

[JasonQiu]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = [(l.val, index) for index, l in enumerate(lists) if l]
        heapq.heapify(heap)
        head = curr = ListNode(None)
        while heap:
            value, index = heapq.heappop(heap)
            curr.next = ListNode(value)
            curr = curr.next
            node = lists[index].next
            lists[index] = lists[index].next
            if node:
                heapq.heappush(heap, (node.val, index))
        return head.next

Time: O(nlogk) Space: O(k)

[harperz24]

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

        n = len(lists)
        interval = 1
        while interval < n:
            for i in range(0, n - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2

        return lists[0]

    def merge2Lists(self, l1, l2):
        dummy = ListNode(0)
        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

        cur.next = l1 if l1 else l2
        return dummy.next

[Hughlin07]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

    if(lists == null){
        return null;
    }

    int len = lists.length;
    int interval = 1; 
    while(interval < len){
        for(int i = 0; i + interval < len; i = i + 2 * interval){
            lists[i] = merge(lists[i], lists[i+interval]);
        }
        interval = interval * 2;
    }
    return len != 0 ? lists[0] : null;
}

public ListNode merge(ListNode l1, ListNode l2){
    ListNode result = new ListNode(0);
    ListNode tail = result;

    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;
    }

    if(l1 != null){
        tail.next = l1;
    }
    else{
        tail.next = l2;
    }
    return result.next;
}

}

[JingYuZhou123]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
function meger(list1, list2) {
    if(list1 === null) {
        return list2
    } else if(list2 === null) {
        return list1
    }
    const pre = new ListNode(0)
    let current = pre
    while(list1 !== null && list2 !== null) {
        if(list1.val < list2.val) {
            current.next = list1
            list1 = list1.next
        } else {
            current.next = list2
            list2 = list2.next
        }
        current = current.next
    }
    if(list1 === null) {
        current.next = list2
    } else {
        current.next = list1
    }
    return pre.next
}

function mergeList(lists, left, right) {
    if(left === right) {
        return lists[left]
    }
    if(left > right) {
        return null
    }
    const mid = Math.floor((left + right) / 2)
    return meger(mergeList(lists, left, mid), mergeList(lists, mid + 1, right))
}

var mergeKLists = function(lists) {
    const n = lists.length
    if(n === 0) {
        return null
    }
    return mergeList(lists, 0, n - 1)
};

[NorthSeacoder]

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    const heap = new minHeap();
    for (let list of lists) {
        while (list) {
            heap.push(list.val);
            list = list.next
        }
    }
    let val = heap.pop();
    const root = new ListNode();
    let cur = root;
    while (val || val === 0) {

        cur.next = new ListNode(val);
        cur = cur.next;
        val = heap.pop();
    };
    return root.next
};
class minHeap {
    constructor() {
        this.heap = [0]
    }
    size() {
        return this.heap[0]
    }
    //小->上
    shiftUp(i) {
        while (i >> 1 > 0) {
            const parentI = i >> 1;
            const parent = this.heap[parentI];
            const cur = this.heap[i];
            if (cur < parent) {
                [this.heap[parentI], this.heap[i]] = [cur, parent]
            }
            i = parentI
        }
    }
    getMinChild(i) {
        const len = this.heap.length - 1
        if (2 * i + 1 > len) return 2 * i;
        if (this.heap[2 * i] > this.heap[2 * i + 1]) return 2 * i + 1;
        return 2 * i;
    }
    //大->下
    shiftDown(i) {
        const len = this.heap.length;
        while (2 * i < len) {
            const childI = this.getMinChild(i);
            const child = this.heap[childI];
            const cur = this.heap[i];
            if (cur > child) {
                [this.heap[childI], this.heap[i]] = [cur, child]
            }
            i = childI
        }
    }

    push(val) {
        this.heap.push(val);
        this.heap[0]++;
        this.shiftUp(this.heap[0])
    }

    pop() {
        const last = this.heap.length - 1;
        if (last === 0) return;
        const res = this.heap[1];
        this.heap[1] = this.heap[last]
        this.heap.pop();
        this.heap[0]--;
        this.shiftDown(1)
        return res
    }
}

[chocolate-emperor]

/**
 * 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) {
        ListNode* sentry = new ListNode();
        ListNode* curr = sentry;
        if(lists.size()==0) return nullptr;
        else if(lists.size()==1)    return lists[0];
        auto cmp = [](const ListNode* a, const ListNode* b){
            return a->val > b->val;
        };
        priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)>pq(cmp);
        //在入队列时保证非空
        int l = lists.size();
        for(int i = 0; i < l; i++){
            if(lists[i])    pq.push(lists[i]);
        }

        while(!pq.empty()){
            ListNode* tmp = pq.top();
            pq.pop();
            curr->next= tmp;
            curr = curr->next;
            if(tmp->next)    pq.push(tmp->next);
        }
        ListNode* head = sentry->next;
        delete sentry;
        sentry = nullptr;
        return head;
    }
};

[SoSo1105]

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

    n = len(lists)
    interval = 1
    while interval < n:
        for i in range(0, n - interval, interval * 2):
            lists[i] = self.merge2Lists(lists[i], lists[i + interval])
        interval *= 2

    return lists[0]

def merge2Lists(self, l1, l2):
    dummy = ListNode(0)
    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

    cur.next = l1 if l1 else l2
    return dummy.next

[snmyj]

class Solution {
public:
    ListNode* mergetwo(ListNode*a,ListNode*b){
          if ((!a)||(!b)) return a?a:b;
          ListNode head(-1),*rear=&head,*pa=a,*pb=b;
          while(pa&&pb){
              if(pa->val<pb->val){
                  rear->next=pa;
                  pa=pa->next;
              }
              else{
                   rear->next=pb;
                  pb=pb->next;
              }
              rear=rear->next;
          }
          rear->next=(pa?pa:pb);
          return head.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
            ListNode *ans=nullptr;
            for(int i=0;i<lists.size();i++){
                ans=mergetwo(lists[i],ans);
            }
            return ans;
    }
};

[bookyue]

TC: O(nlogn)
SC: O(n)

    public ListNode mergeKLists(ListNode[] lists) {
        var minHeap = new PriorityQueue<ListNode>(Comparator.comparingInt(a -> a.val));

        for (var head : lists)
            if (head != null) minHeap.offer(head);

        ListNode dummy = new ListNode(-1);
        var cur = dummy;
        while (!minHeap.isEmpty()) {
            cur.next = minHeap.poll();

            cur = cur.next;
            if (cur.next != null) minHeap.offer(cur.next);
        }

        return dummy.next;
    }

[Lydia61]

23. 合并K个排序链表

思路

顺序合并

代码

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    if ((!a) || (!b)) return a ? a : b;
    ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr; aPtr = aPtr->next;
        } else {
            tail->next = bPtr; bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}
···

## 复杂度分析

- 时间复杂度：O(n)
- 空间复杂度：O(1)

[kangliqi1]

class Solution {

public ListNode mergeKLists(ListNode[] lists) {

if(lists == null){
    return null;
}

int len = lists.length;
int interval = 1; 
while(interval < len){
    for(int i = 0; i + interval < len; i = i + 2 * interval){
        lists[i] = merge(lists[i], lists[i+interval]);
    }
    interval = interval * 2;
}
return len != 0 ? lists[0] : null;

}

public ListNode merge(ListNode l1, ListNode l2){ ListNode result = new ListNode(0); ListNode tail = result;

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;
}

if(l1 != null){
    tail.next = l1;
}
else{
    tail.next = l2;
}
return result.next;

} }

[KrabbeJing]

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)

        if lenth == 0: return None
        if lenth == 1: return lists[0]
        if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])

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

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(0)
        c1, c2, c3 = l1, l2, res
        while c1 or c2:
            if c1 and c2:
                if c1.val < c2.val:
                    c3.next = ListNode(c1.val)
                    c1 = c1.next
                else:
                    c3.next = ListNode(c2.val)
                    c2 = c2.next
                c3 = c3.next
            elif c1:
                c3.next = c1
                break
            else:
                c3.next = c2
                break

        return res.next

[joemonkeylee]

代码

        public ListNode MergeKLists(ListNode[] lists)
        {
            if (lists.Length == 0)
            {
                return null;
            }
            ListNode dummyHead = new ListNode(0);
            PriorityQueue<ListNode, int> pq = new PriorityQueue<ListNode, int>();
            foreach (ListNode head in lists)
            {
                if (head != null)
                {
                    pq.Enqueue(head, head.val);
                }
            }
            ListNode temp = dummyHead;
            while (pq.Count > 1)
            {
                ListNode node = pq.Dequeue();
                temp.next = node;
                temp = temp.next;
                node = node.next;
                if (node != null)
                {
                    pq.Enqueue(node, node.val);
                }
            }
            if (pq.Count > 0)
            {
                temp.next = pq.Dequeue();
            }
            return dummyHead.next;

        }

复杂度分析

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

[Zoeyzyzyzy]

class Solution {
    //利用堆来处理
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if(list != null) pq.offer(list);
        }
        ListNode newHead = new ListNode(-1), ptr = newHead;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            ptr.next = cur;
            ptr = ptr.next;
            if (cur.next != null)
                pq.offer(cur.next);
        }
        return newHead.next;
    }
}

class Solution1 {
    // 先合并两个有序链表，再遍历合并接下来的链表 - 分治法合并
    // 将k个链表两两配对，并将同一队中的链表合并，第一轮后还剩k/2 对链表待合并
    ListNode[] Lists;

    public ListNode mergeKLists(ListNode[] lists) {
        this.Lists = lists;
        return merge(0, lists.length - 1);
    }

    private ListNode merge(int left, int right) {
        if (left == right)
            return Lists[left];
        if (left > right)
            return null;
        int mid = left + right >> 1;
        return merge2Lists(merge(left, mid), merge(mid + 1, right));
    }

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

class Solution2 {
    // 先合并两个有序链表，再遍历合并接下来的链表
    // Time Complexity: O((m+n)^k) Space Complexity: O(1)
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        ListNode cur = lists[0];
        for (int i = 1; i < lists.length; i++) {
            cur = merge2Lists(cur, lists[i]);
        }
        return cur;
    }

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

[CruiseYuGH]

关键点

代码

• 语言支持：Python3

Python3 Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoList(self,list_1,list_2):
        if not list_1: return list_2
        if not list_2: return list_1
        if list_1.val < list_2.val :
            list_1.next = self.mergeTwoList(list_1.next,list_2)
            return list_1
        else:
            list_2.next = self.mergeTwoList(list_1,list_2.next)
            return list_2
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoList(l1, l2)
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return
        n = len(lists)
        return self.merge(lists,0,n-1)

[liuajingliu]

代码实现

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(logk)$
• 时间复杂度: $O(O(kn×logk))$

[lp1506947671]

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)

        # basic cases
        if lenth == 0: return None
        if lenth == 1: return lists[0]
        if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])

        # divide and conqure if not basic cases
        mid = n // 2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(0)
        c1, c2, c3 = l1, l2, res
        while c1 or c2:
            if c1 and c2:
                if c1.val < c2.val:
                    c3.next = ListNode(c1.val)
                    c1 = c1.next
                else:
                    c3.next = ListNode(c2.val)
                    c2 = c2.next
                c3 = c3.next
            elif c1:
                c3.next = c1
                break
            else:
                c3.next = c2
                break

        return res.next

复杂度分析

• 时间复杂度：O(kn*logk)
• 空间复杂度：O(logk)

[Jetery]

class Solution {
public:
    struct cmp { //结构体 cmp 重载 ()函数
        bool operator()(ListNode *a, ListNode *b) {
            return a->val > b->val; // 小根堆
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;

        for (ListNode *list : lists) 
            if (list != nullptr)
                q.push(list);

        ListNode *dummy = new ListNode(0), *tail = dummy;
        while (!q.empty()) {
            ListNode *cur = q.top(); q.pop();
            tail->next = cur;
            tail = tail->next;
            if (cur->next != nullptr) //if (cur->next)
                q.push(cur->next);
        }

        return dummy->next;
    }
};

[aoxiangw]

# 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 or len(lists) == 0:
            return None

        while len(lists) > 1:
            merge = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                merge.append(self.mergeTwoLists(l1, l2))
            lists = merge
        return lists[0]

    def mergeTwoLists(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
        elif l2:
            tail.next = l2
        return dummy.next

[X1AOX1A]

# 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:
        n = len(lists)

        # basic cases
        if lenth == 0: return None
        if lenth == 1: return lists[0]
        if lenth == 2: return self.mergeTwoLists(lists[0], lists[1])

        # divide and conqure if not basic cases
        mid = n // 2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n]))

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        res = ListNode(0)
        c1, c2, c3 = l1, l2, res
        while c1 or c2:
            if c1 and c2:
                if c1.val < c2.val:
                    c3.next = ListNode(c1.val)
                    c1 = c1.next
                else:
                    c3.next = ListNode(c2.val)
                    c2 = c2.next
                c3 = c3.next
            elif c1:
                c3.next = c1
                break
            else:
                c3.next = c2
                break

        return res.next

[tzuikuo]

思路

分治

代码

class cmp {
     public:
     bool operator()(ListNode* a, ListNode* b)
     {
         if(a->val > b->val)return true;
         else return false;
     }
 };
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
     {
        priority_queue<ListNode* , vector<ListNode*>,cmp> q;
        ListNode* dummy = new ListNode(-1);
        ListNode* tail = dummy;
        for(int i = 0 ; i<lists.size() ; i++)
        {
            if(lists[i] != NULL)
            {
                q.push(lists[i]);
            }
        }
        while(q.size() > 0)
        {
            ListNode* temp = q.top();
            tail->next = temp;
            tail = temp;
            q.pop();
            if(temp->next != NULL)q.push(temp->next);
        }return dummy->next;
    }
};

复杂度分析 -待定