azl397985856 commented 2 years ago

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

yetfan commented 2 years ago

思路全部数扔进堆里面，最小堆创建新的listnode

代码

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)

QinhaoChang commented 2 years ago

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

    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(minheap, (lists[i].val, i))

    dummy = ListNode(-1)
    head = dummy

    while minheap:
        val, index = heapq.heappop(minheap)
        head.next = ListNode(val)
        head = head.next
        lists[index] = lists[index].next
        if lists[index]:
            heapq.heappush(minheap, (lists[index].val, index))
    return dummy.nex

zwx0641 commented 2 years ago

/**

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 queue = new PriorityQueue<>(new Comparator() { public int compare(ListNode l1, ListNode l2) { return l1.val - l2.val; } });

for (ListNode node : lists) {
    if (node == null) continue;
    queue.offer(node);
}

ListNode head = new ListNode();
ListNode cur = head;
while (!queue.isEmpty()) {
    ListNode node = queue.poll();
    cur.next = node;
    cur = cur.next;
    if (node.next != null) {
        queue.offer(node.next);
    }
}
return head.next; */
int len = lists.length;
if (len == 0) return null;
if (len == 1) return lists[0];
if (len == 2) return mergeTwoLists(lists[0], lists[1]);

int mid = len / 2;
ListNode[] list1 = new ListNode[mid];
ListNode[] list2 = new ListNode[len - mid];
for (int i = 0; i < mid; i++) {
    list1[i] = lists[i];
}
for (int i = mid, j = 0; i < len; i++, j++) {
    list2[j] = lists[i];
}
return mergeTwoLists(mergeKLists(list1), mergeKLists(list2));

}

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

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

} }

ZacheryCao commented 2 years ago

Idea:

Divide Conqur

Code:

#include <math.h>
/**
 * 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) {
        int n = lists.size();
        if(n <1) return NULL;
        if(n<2) return lists[0];
        int k = 0;
        while(n>1){
            for(int i = 0; i+pow(2,k)<lists.size(); i=i+pow(2,k+1)){
                lists[i] = merge2Lists(lists[i],lists[i+pow(2,k)]);
            }
            n = div(n+1, 2).quot;
            k++;
        }
        return lists[0];
    }

     ListNode* merge2Lists(ListNode* list1, ListNode* list2) {
         ListNode* head = new ListNode();
         ListNode* dummy = head;
         while(list1!=NULL and list2!=NULL){
             if(list1->val > list2->val){
                 head->next = new ListNode(list2->val);
                 list2 = list2->next;
             }

             else{
                 head->next = new ListNode(list1->val);
                 list1 = list1->next;
             }
             head = head->next;
         }
         while(list1!=NULL){
             head->next = new ListNode(list1->val);
             list1 = list1->next;
             head = head->next;
         }
         while(list2!=NULL){
             head->next = new ListNode(list2->val);
             list2 = list2->next;
             head = head->next;
         }
         return dummy->next;
    }
};

Complexity:

Time: O(N log K) Space: O(1)

hulichao commented 2 years ago

思路

思路，保存顶部指针，每次生产新节点都去顶部遍历一下, 打地鼠思维

代码

/**
 * 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 {

    // 思路，保存顶部指针，每次生产新节点都去顶部遍历一下 复杂度 k * Sum(n1 + n2...)
    // 思路归并，思路堆
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode[] top = new ListNode[k];
        for (int i = 0; i < k; i++) {
            if (lists[i] != null) {
                top[i] = lists[i];
            } 
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        while(topIsEmpty(top)) {
            int minVa = Integer.MAX_VALUE, index = 0;
            for (int i = 0; i < k; i++) {
                if (top[i] == null) continue;
                if (top[i].val < minVa) {
                    minVa = top[i].val;
                    index = i;
                }
            }

            cur.next = new ListNode(minVa);
            cur = cur.next;
            top[index] = top[index].next;
        }

        return head.next;

    }

    // 判断k个指针是不是全部都为空 如果全部为空的话 就退出while
    private boolean topIsEmpty(ListNode[] nodes) {
        for (ListNode node : nodes) {
            if (node != null) return true;
        }
        return false;
    }
}

复杂度分析

时间复杂度：k * Sum(n1 + n2...)，其中 N 为数组长度。
空间复杂度：O(N)

feifan-bai commented 2 years ago

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

    # basic cases
    if n == 0: return None
    if n == 1: return lists[0]
    if n == 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

ZJP1483469269 commented 2 years ago

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

ZJP1483469269 commented 2 years ago

# 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]:
        n = len(lists)
        def megretwo(ls , l , r):
            if l >= r:
                return
            mid = (l + r) // 2
            megretwo(ls , l , mid)
            megretwo(ls , mid + 1 , r)
            tmp = ListNode(0)
            head = tmp
            i , j = ls[l] , ls[mid + 1] 
            while i or j :
                if i and(not j or i.val <= j.val): 
                    tmp.next = ListNode(i.val)
                    i = i.next
                    tmp = tmp.next
                else:
                    tmp.next = ListNode(j.val)
                    j = j.next
                    tmp = tmp.next
            for i in range(l , r + 1):
                ls[i] = head.next

        if n < 1:
            return None
        if n == 1:
            return lists[0]
        else:
            megretwo(lists , 0 , n - 1)
            return lists[0]

FlorenceLLL commented 2 years ago

思路

Use priority queue. Each time put the first one of each LinkedList into priority queue:

since all LinkedLists are sorted, now priority queue has the smallest ListNode value.
each time poping up one ListNode, add its next into priority queue

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comaprator<ListNode>() {
            @Override
            public int compare(ListNode l1, ListNode l2) {
                if (l1.val < l2.val) return -1;
                else if (l1.val == l2.val) return 0;
                else return 1;
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        for (ListNode node: lists) {
            queue.add(node);
        }

        while (!queue.isEmpty()) {
            current.next = queue.poll();
            current = current.next;
            if (current.next != null) queue.add(current.next);
        }
    }
}

复杂度分析

时间复杂度 O(Nlogk) 空间复杂度 O(N)

zhangzz2015 commented 2 years ago

思路

采用K merge方法，使用priority_queue，时间复杂度为O(n*logk) 空间复杂度为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) {

        // priority que. 
        auto comp = [](ListNode* & node1, ListNode* & node2)
        {
            return node1->val > node2->val;             
        }; 
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp); 

        for(int i=0; i< lists.size(); i++)
        {
            if(lists[i]!=NULL)
            {
                pq.push(lists[i]); 
            }
        }
        ListNode* prev = NULL; 
        ListNode* head = NULL; 
        while(pq.size())
        {
            auto topNode = pq.top(); 
            pq.pop(); 
            if(prev!=NULL)
                prev->next = topNode; 
            else
            {
                head = topNode; 
            }
            prev = topNode; 
            if(topNode->next)
            {
                pq.push(topNode->next); 
            }            
        }

        return head; 
    }
};

rzhao010 commented 2 years ago

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[end];
        }
        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;
        }
    }
}

Complexity Time: O(nklogk) Space: O(logk)

yijing-wu commented 2 years ago


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

}

ZhangNN2018 commented 2 years ago

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

        def merge(left, right):
            if left > right:
                return
            if left == right:
                return lists[left]
            mid = (left + right) // 2
            l1 = merge(left, mid)
            l2 = merge(mid + 1, right)
            return mergeTwoLists(l1, l2)

        def mergeTwoLists(l1, l2):
            if not l1 or not l2:
                return l1 or l2
            if l1.val < l2.val:
                l1.next = mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = mergeTwoLists(l1, l2.next)
                return l2

        return merge(0, n - 1)

Tesla-1i commented 2 years ago

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        def megretwo(ls , l , r):
            if l >= r:
                return
            mid = (l + r) // 2
            megretwo(ls , l , mid)
            megretwo(ls , mid + 1 , r)
            tmp = ListNode(0)
            head = tmp
            i , j = ls[l] , ls[mid + 1] 
            while i or j :
                if i and(not j or i.val <= j.val): 
                    tmp.next = ListNode(i.val)
                    i = i.next
                    tmp = tmp.next
                else:
                    tmp.next = ListNode(j.val)
                    j = j.next
                    tmp = tmp.next
            for i in range(l , r + 1):
                ls[i] = head.next

        if n < 1:
            return None
        if n == 1:
            return lists[0]
        else:
            megretwo(lists , 0 , n - 1)
            return lists[0]

yan0327 commented 2 years ago

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0{
        return nil
    }
    if len(lists) == 1{
        return lists[0]
    }
    n := len(lists)
    l1 := append([]*ListNode{},lists[:n/2]...)
    l2 := append([]*ListNode{},lists[n/2:]...)
    return merge(mergeKLists(l1),mergeKLists(l2))
}
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
}

moirobinzhang commented 2 years ago

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

}

xuhzyy commented 2 years ago

# 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

1149004121 commented 2 years ago

合并K个升序链表

思路

分而治之。

代码

var mergeKLists = function(lists) {
    const n = lists.length;
    if(n == 1) return lists[0];
    if(n == 0) return null;
    let mid = n >>> 1;
    let list1 = mergeKLists(lists.slice(0, mid));
    let list2 = mergeKLists(lists.slice(mid));
    let p1 = list1, p2 = list2;
    let dummy = new ListNode(0);
    let newList = dummy;
    while(p1 && p2){
        if(p1.val < p2.val){
            newList.next = p1;
            p1 = p1.next;
        }else{
            newList.next = p2;
            p2 = p2.next;
        };
        newList = newList.next;
    };
    if(p1) newList.next = p1;
    if(p2) newList.next = p2;
    return dummy.next;
};

复杂度分析

时间复杂度：O(K N logN)。
空间复杂度：O(logK)。

CoreJa commented 2 years ago

思路

这个题算做好几遍了，主要的做法就是小顶堆和归并两个思路，设lists长度为$n$，单个链表最长为$k$，则复杂度为$O(kn\log n)$

归并：和归并排序类似，把链表两两合并，最后合并为整体。两两合并的递归过程，最底层是$\frac{n}{2}k$，即$n/2$个长度为k的链表合并，一般化公式则是第i层的合并是$\frac{n}{2i}$个长度为$ik$的链表合并，递归树一共有$\log n$层，总复杂度$O(kn\log n)$
小顶堆：维护一个长度为n的小顶堆，入堆lists的每个头结点。每次出堆最小的结点，并把该节点的后续入堆，堆大小为$O(n)$，有$nk$个节点要进行入堆出堆操作，所以复杂度为$kn\log n$。

代码

class Solution:
    # 归并：和归并排序类似，把链表两两合并，最后合并为整体。两两合并的递归过程，最底层是$\frac{n}{2}*k$，即$n/2$个长度为k的
    # 链表合并，一般化公式则是第`i`层的合并是$\frac{n}{2i}$个长度为$i*k$的链表合并，递归树一共有$\log n$层，
    # 总复杂度$O(kn\log n)$
    def mergeKLists1(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(a, b):
            ans = ListNode()
            p = ans
            while a and b:
                if a.val < b.val:
                    p.next = a
                    a = a.next
                else:
                    p.next = b
                    b = b.next
                p = p.next
            p.next = a if a else b
            return ans.next

        n = len(lists)
        if n == 0:
            return None
        if n == 1:
            return lists[0]
        return merge(self.mergeKLists(lists[:n // 2]), self.mergeKLists(lists[n // 2:]))

    # 小顶堆：维护一个长度为n的小顶堆，入堆`lists`的每个头结点。每次出堆最小的结点，并把该节点的后续入堆，堆大小为$O(n)$，
    # 有$nk$个节点要进行入堆出堆操作，所以复杂度为$kn\log n$。
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap_min = [(node.val, i) for i, node in enumerate(lists) if node]
        heapq.heapify(heap_min)
        ans = ListNode()
        p = ans
        while heap_min:
            val, i = heap_min[0]
            p.next = ListNode(val)
            p = p.next
            lists[i] = lists[i].next
            if lists[i]:
                heapq.heapreplace(heap_min, (lists[i].val, i))
            else:
                heapq.heappop(heap_min)
        return ans.next

watchpoints commented 2 years ago

大小为k的堆

代码

/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
/**
 * 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:
    /**
     *   //01 定义数据结构
     *     //02 初始化数组链表
     * */

   ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        // 小根堆的回调函数
        auto comp = [&](ListNode *a, ListNode *b) {
            return a->val > b->val;
        };
        priority_queue<ListNode *, vector<ListNode *>, decltype(comp)> pq(comp);

        //在链表后面追加 需要头节点
        ListNode head;
        ListNode *ptail = &head;

        //建立大小为k的小根堆
        for (ListNode *ptemp : lists)
        {
            if (ptemp)
            {
                pq.push(ptemp);
            }
        }

        while (!pq.empty())
        {
            //01 get
            ListNode *pcur = pq.top();
            pq.pop();
            //02 push
            if (pcur && pcur->next)
            {
                pq.push(pcur->next);
            }

            //03  在链表最后位置追加，不是前面添加。
            //pcur->next =ptail->next;
            ptail->next = pcur;
            ptail = pcur;
        }
        return head.next;
    }
};
// @lc code=end

charlestang commented 2 years ago

思路

最小堆。

取出每条队列的第一个节点，然后加入堆。

将堆顶作为合并后的下一个元素，然后将堆顶元素所在队列的下一个元素加入堆。

重复这个过程，直到堆为空。

时间复杂度 K条队列，平均每条队列有 n 个元素，O(Kn logK)

空间复杂度 O(K)

class LNode:
    def __init__(self, val=0, pointer=None):
        self.val = val
        self.pointer = pointer
    def __lt__(self, other):
        return self.val < other.val

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        q = []
        heapq.heapify(q)
        for l in lists:
            if l != None:
                heapq.heappush(q, LNode(l.val, l))

        tail = res = ListNode()
        while q:
            cur = heapq.heappop(q)
            tail.next = cur.pointer
            tail = tail.next
            if cur.pointer.next != None:
                heapq.heappush(q, LNode(cur.pointer.next.val, cur.pointer.next))
        tail.next = None

        return res.next

思路2

归并排序

反复两两合并。

时间复杂度 O(Kn)

空间复杂度 O(logK)

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

haixiaolu commented 2 years ago

思路

同时比k组，归并排序，结合21. Merge two sorted list

代码/python

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

复杂度分析

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

zjsuper commented 2 years ago

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.merge2(lists[0],lists[1])

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

    def merge2(self,l,r):
        res = ListNode(0)
        c = res
        while l and r:
            if l.val <= r.val:
                c.next = l
                c= c.next
                l = l.next
            elif l.val> r.val:
                c.next = r
                c= c.next
                r = r.next
        if l:
            c.next = l
        elif r:
            c.next = r
        return res.next

cszys888 commented 2 years ago

# 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
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next

        while head:
            val, idx = heapq.heappop(head)
            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

time complexity: O(Nlogk), N stands for total number of elements in all linkedlist space complexity: O(k)

pwqgithub-cqu commented 2 years ago

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

alongchong commented 2 years ago

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

KennethAlgol commented 2 years ago


class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> (a.val - b.val));
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!minHeap.isEmpty()) {
            ListNode temp = minHeap.poll();
            cur.next = temp;
            if (temp.next != null) {
                minHeap.offer(temp.next);
            }
            cur = cur.next;
        }
        return dummy.next;
    }

}

LinnSky commented 2 years ago

思路

取值排序，然后重建链表

代码

     var mergeKLists = function(lists) {
        const list = []
        for(let i = 0; i < lists.length; i++) {
            let node = lists[i]
            while(node) {
                list.push(node.val)
                node = node.next
            }
        }
        list.sort((a, b) => a - b)
        const res = new ListNode()
        let now = res
        for(let i = 0; i < list.length; i++) {
            now.next = new ListNode(list[i])
            now = now.next
        }
        return res.next
    };

复杂度分析

-时间复杂度O(NlogN) -空间复杂度O(N)

Richard-LYF commented 2 years ago

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: if not lists: return n = len(lists) return self.merge(lists, 0, n-1)

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.mergeTwoLists(l1,l2)

def mergeTwoLists(self,l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val<l2.val:
        l1.next = self.mergeTwoLists(l1.next,l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1,l2.next)
        return l2

o knlogk logk

heap: nlogk o kn

Menglin-l commented 2 years ago

approach: merge with divide and conquer

code:

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

        return mergeLists(lists, 0, lists.length - 1);
    }

    public ListNode mergeLists(ListNode[] lists, int begin, int end) {
        if (begin == end) {
            return lists[begin];
        }

        int mid = begin + (end - begin) / 2;
        ListNode left = mergeLists(lists, begin, mid);
        ListNode right = mergeLists(lists, mid + 1, end);
        return mergeTwoLists(left, right);
    }

    public ListNode mergeTwoLists(ListNode l, ListNode r) {
        if (l == null && r != null) return r;
        if (l != null && r == null) return l;
        if (l == null && r == null) return null;

        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (l != null && r != null) {
            if (l.val <= r.val) {
                curr.next = l;
                l = l.next;
            } else {
                curr.next = r;
                r = r.next;
            }

            curr = curr.next;
        }

        if (l != null) curr.next = l;
        if (r != null) curr.next = r;

        return dummy.next;
    }
}

complexity:

Time: O(NlogN)

Space: O(1)

JudyZhou95 commented 2 years ago

代码

from heapq import heappush, heappop, heapreplace, heapify
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

        heap = [(head.val, i, head) for i, head in enumerate(lists) if head]
        heapify(heap)

        tail = ListNode(0)
        head = tail

        while heap:
            val, i, node = heap[0]
            if not node.next:
                heappop(heap)

            else:
                heapreplace(heap, (node.next.val, i, node.next))

            tail.next = node
            tail = tail.next
        return head.next

    """
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:

        # Divide and conquer, build a merge two sorted list helper function. Then Divede k lists until the length is <= 2. Then merge two by two.
        # should ask whether we have to use the original nodes or we can create new nodes using originnal val

        n = len(lists)

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

        mid = n//2

        return self.mergeTwoSortedLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))

    def mergeTwoSortedLists(self, l1, l2):        
        res = ListNode(0)        
        d1, d2, d3 = l1, l2, res

        while d1 and d2:          
            if d1.val < d2.val:
                d3.next = d1
                d1 = d1.next
            else:
                d3.next = d2
                d2 = d2.next
            d3 = d3.next

        if d1:
            d3.next = d1
        if d2:
            d3.next = d2

        return res.next
    """

LannyX commented 2 years ago

思路

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

ivangin commented 2 years ago

code:

public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }
        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }
        return dummy.next;
    }

luhnn120 commented 2 years ago

思路

分治 + 合并链表

代码

/**
 * @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(logk) 时间复杂度 O(O(kn×logk))

falconruo commented 2 years ago

思路:

分治思想

复杂度分析:

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

代码(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* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;

        int len = lists.size();

        while (len > 1) {
            int mid = (len + 1)/2;
            for (int i = 0; i < len / 2; i++) {
                lists[i] = merge2(lists[i], lists[i + mid]);
            }
            len = mid;
        }
        return lists[0];
    }
private:
    ListNode* merge2(ListNode* p, ListNode* q) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;

        while (p && q) {
            if (p->val < q->val) {
                cur->next = p;
                p = p->next;
            } else {
                cur->next = q;
                q = q->next;
            }
            cur = cur->next;
        } 

        cur->next = p ? p : q;

        return dummy->next;
    }
};

machuangmr commented 2 years ago

代码

归并排序
/**
 * 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;
    }
}

yinhaoti commented 2 years ago

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

    ## TC:klogk * n -> O(kn * logk)
    ## SC: logk
    """
    思路：
    1. 写mergeTwo
    2. mergeSort
    """
    def mergeTwoLists(self, 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

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        l = len(lists)
        if l == 0: return None
        if l == 1: return lists[0]
        if l == 2: return self.mergeTwoLists(lists[0], lists[1])

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

hdyhdy commented 2 years ago

分支

func mergeKLists( lists []*ListNode ) *ListNode {
    length := len(lists)
    if length == 0 {return nil}
    if length == 1 {return lists[0]}
    mid := length>>1                                              //分治
    return meger(mergeKLists(lists[:mid]), mergeKLists(lists[mid:]))  //归并
}

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

declan92 commented 2 years ago

思路

1. 将数组分成左右两个子数组;(怎么分)
2. 分别合并两个子数组成升序链表链表;(子问题与原问题同一性质)
3. 数组长度为1时,直接返回链表;(边界)
4. 合并两个链表,通过双指针完成;(合并子问题解)

步骤

1. 数组长度为1,直接返回链表;
2. 数组分成左右两个数组,递归求升序链表;
3. 使用双指针将两个链表合并成一个升序链表

java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        if (lists.length == 1)
            return lists[0];
        int n = lists.length;
        int left = 0, right = n - 1;
        int mid = left + ((right - left) >> 1);
        ListNode leftNode = mergeKLists(Arrays.copyOfRange(lists, 0, mid + 1));
        ListNode rightNode = mergeKLists(Arrays.copyOfRange(lists, mid + 1, n));
        return mergeTwoLists(leftNode, rightNode);
    }

    public ListNode mergeTwoLists(ListNode leftNode, ListNode rightNode) {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (leftNode != null || rightNode != null) {
            if (leftNode != null && rightNode != null) {
                if (leftNode.val <= rightNode.val) {
                    cur.next = leftNode;
                    leftNode = leftNode.next;
                } else {
                    cur.next = rightNode;
                    rightNode = rightNode.next;
                }
                cur = cur.next;
            } else if (leftNode != null) {
                cur.next = leftNode;
                break;
            } else if (rightNode != null) {
                cur.next = rightNode;
                break;
            }
        }
        return head.next;
    }
}

时间:$O(k*nlogk)$,k为数组长度,n为链表长度;
空间:$O(logk)$

Aobasyp commented 2 years ago

思路归并排序

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

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

Myleswork commented 2 years ago

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

callmeerika commented 2 years ago

思路

分治

代码

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)

junbuer commented 2 years ago

思路

堆排序

代码

# 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
    """
    q = []
    res = ListNode()
    for li in lists:
        while li:
            heapq.heappush(q, li.val)
            li = li.next

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

复杂度分析

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

liuajingliu commented 2 years ago

代码实现

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))$

15691894985 commented 2 years ago

优先队列合并：

，维护当前每个链表没有合并的最前面的一个元素每次在其中选择VAL值最小的，用队列来优化这个过程。

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

      dummy = ListNode(0, None)
      cur = dummy
      while heap:
          VALUE = heapq.heappop(heap)
          cur.next = ListNode(VALUE, None)
          cur = cur.next
      return dummy.next

时间复杂度：O(n*logn)
空间复杂度：O(n)

Hacker90 commented 2 years ago

分支

func mergeKLists( lists []ListNode ) ListNode { length := len(lists) if length == 0 {return nil} if length == 1 {return lists[0]} mid := length>>1 //分治 return meger(mergeKLists(lists[:mid]), mergeKLists(lists[mid:])) //归并 }

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

dahaiyidi commented 2 years ago

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

shamworld commented 2 years ago

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

guangsizhongbin commented 2 years ago

/**

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

ozhfo commented 2 years ago

/**
 * 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 == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) return -1;
                else if (o1.val == o2.val) return 0;
                else return 1;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }
        while (!queue.isEmpty()) {
            p.next = queue.poll();
            p = p.next;
            if (p.next != null) queue.add(p.next);
        }
        return dummy.next;
    }
}

leetcode-pp / 91alg-6-daily-check

【Day 69 】2022-02-18 - 23. 合并 K 个排序链表 #79

23. 合并 K 个排序链表

入选理由

题目地址

前置知识

题目描述

Idea:

Code:

Complexity:

思路

代码

思路

代码

复杂度分析

思路

关键点

代码

思路

代码

大小为k的堆

代码

思路

思路2

思路

代码/python

复杂度分析

思路

代码

复杂度分析

Definition for singly-linked list.

class ListNode:

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

self.val = val

self.next = next

o knlogk logk

heap: nlogk o kn

approach: merge with divide and conquer

code:

complexity:

Time: O(NlogN)

Space: O(1)

代码

思路

代码

思路

代码

复杂度

代码

思路

代码

复杂度

思路

代码

复杂度分析

代码实现

复杂度分析

Problem

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

Note

Complexity

Python

C++