【Day 69 】2022-09-21 - 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

[laofuWF]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        d = {}
        for k in range(len(lists)):
            if lists[k]:
                d[k] = lists[k]
                heap.append((lists[k].val, k))
        heapq.heapify(heap)

        head = curr = ListNode()
        while heap:
            _, k = heapq.heappop(heap)
            curr.next = d[k]
            curr = curr.next
            d[k] = d[k].next
            if d[k]:
                heapq.heappush(heap, (d[k].val, k))
        curr.next = None
        return head.next

[thinkfurther]

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

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

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

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

时间复杂度：O(n∗logk) 空间复杂度：O(logk)

[joeymoso]

# 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]:
        lenth = len(lists)
        if lenth == 0: return None
        if lenth == 1: return lists[0]
        if lenth == 2: return self.merge_two_list(lists[0], lists[1])

        mid = lenth // 2
        return self.merge_two_list(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))
    def merge_two_list(self, list1, list2):
        head = ListNode()
        cur = head
        while list1 and list2:
            cur.next = ListNode()
            cur = cur.next
            cur_min = float('inf')
            if list1.val <= list2.val:
                cur_min = list1.val
                list1 = list1.next
            else:
                cur_min = list2.val
                list2 = list2.next
            cur.val = cur_min    
        if list1:
            cur.next = list1
            return head.next
        if list2:
            cur.next = list2
            return head.next
        return head.next

[xxiaomm]

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>
            ((a,b) -> (a.val - b.val));
        for (ListNode head: lists) {
            if (head != null)
                pq.offer(head);
        }

        ListNode dummy = new ListNode(-1), cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            cur.next = node;
            if (node.next != null)
                pq.offer(node.next);
            cur = cur.next;
        }
        return dummy.next;
    }
}

[testplm]

var mergeKLists = function (lists) {
    function mergeTwoLists(l1, l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val<l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1,l2.next );
        return l2;
    }
    if(lists.length == 0) return null;

    while(lists.length > 1) {
        lists.push(mergeTwoLists(lists.shift(), lists.shift()));
    }
    return lists[0];
};

[MichaelXi3]

Idea

Merge Sort 分治思想

Code

/**
 * 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 mergeSort(lists, 0, lists.length - 1);
    }

    // MergeSort Divide: O(logN)
    public ListNode mergeSort(ListNode[] lists, int l, int r) {
        // ListNode[] array only has one element
        if (l == r) { return lists[l];}

        if (l < r) {
            int m = l + (r - l) / 2;
            ListNode left = mergeSort(lists, l, m);
            ListNode right = mergeSort(lists, m+1, r);
            return mergeTwo(left, right);
        } else {
            // ListNode[] array has no element, thus l > r
            return null;
        }
    }

    // MergeSort Conquer: O(N)
    public ListNode mergeTwo (ListNode list1, ListNode list2) {
        if (list1 == null) { return list2;}
        if (list2 == null) { return list1;}

        if (list1.val < list2.val) {
            list1.next = mergeTwo(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwo(list1, list2.next);
            return list2;            
        }
    }
}

[LiquanLuo]

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

    struct cmp {
      bool operator()(ListNode* l1, ListNode* l2) {
          return l1->val > l2->val;
      }   
    };

    priority_queue<ListNode*, vector<ListNode*>,cmp> pq;

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto head = new ListNode();
        auto cur = head;
        // auto cmp = [](ListNode* l1, ListNode* l2) {return l1->val > l2->val;};

        for (auto list : lists) {
            if (list != nullptr) {
                pq.push(list);
            }

        }
        while (!pq.empty()) {
            auto node = pq.top();
            pq.pop();
            if (node != nullptr && node->next != nullptr) {
                pq.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }

        return head->next;
    }
};

/***
Solution:
DS:
1. pq

ALgo:
1. put all the nodes into pq
2. pop the lowest one, and push it->next to the pq

Time: O(nlognK) k= len(lists)
Space: O(k)

**/

[dereklisdr]

class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0){ return null; } ListNode dummy = new ListNode(-1); ListNode cur = 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();

        cur.next = node;
        cur = cur.next;

        if (node.next != null){
            pq.add(node.next);
        }
    }
    return dummy.next;

}

}

[Whisht]

采用优先队列动态求极值。

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

        head = ListNode()
        p = head
        heap = []
        for i, pi in enumerate(lists):
            if pi:
                heapq.heappush(heap, (pi.val, i))
                lists[i] = lists[i].next

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

[lbc546]

everything into a list and sort

Python

   """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

Complexity

Time: O(nlogn) Space: O(n)

[flaming-cl]

class Solution {
    // T: O(kn×logk)
    // S: O(logk)
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 0) return null;
        return divAndConMerge(lists, 0, n - 1);
    }

    private ListNode divAndConMerge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        return mergeTwoLists(divAndConMerge(lists, left, mid), divAndConMerge(lists, mid + 1, right));
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode();
        ListNode temp = newList;
        while (l1 != null && l2 != null) {
             if (l1.val < l2.val) {
                 temp.next = l1;
                 l1 = l1.next;
             } else {
                 temp.next = l2;
                 l2 = l2.next;
             }
             temp = temp.next;
        }
        temp.next = l1 == null ? l2 : l1;
        return newList.next;
    }
}

[zch-bit]

// MergeKSortedLinkedList merges k sorted lists - LeetCode 23
func MergeKSortedLinkedList(lists []*listnode) *listnode {
    // 1. dummy listnode
    dummyHead := &listnode{val: 0}
    curr := dummyHead

    // 2. push into min heap
    hp := &minHeap{}
    for _, val := range lists {
        *hp = append(*hp, val)
    }
    heap.Init(hp)

    // 3. pop and assign to curr
    for len(*hp) > 0 {
        i := heap.Pop(hp).(*listnode)
        curr.next = &listnode{val: i.val} // create a new listnode
        curr = curr.next

        if i.next != nil {
            heap.Push(hp, i.next)
        }
    }
    return dummyHead.next
}

[jackgaoyuan]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type MinHeap23 struct {
    Arr []*ListNode
}

func initMinHeap23() MinHeap23 {
    return MinHeap23{Arr: make([]*ListNode, 1)}
}

func (mh *MinHeap23) Insert23(node *ListNode) {
    arr := append(mh.Arr, node)
    PercolateUp23(arr, len(arr)-1)
    mh.Arr = arr
}

func (mh *MinHeap23) Pop() *ListNode {
    if len(mh.Arr) <= 1 {
        return nil
    }
    arr := mh.Arr
    res := arr[1]
    arr[1] = arr[len(arr)-1]
    arr = arr[:len(arr)-1]
    PercolateDown23(arr, 1)
    mh.Arr = arr
    return res
}

func (mh *MinHeap23) isEmpty() bool {
    return len(mh.Arr) <= 1
}

func PercolateDown23(arr []*ListNode, i int) {
    if len(arr) <= 1 || i >= len(arr) {
        return
    }
    var smallerIndex int
    leftIndex := 2 * i
    rightIndex := 2*i + 1
    if leftIndex >= len(arr) {
        return
    } else if rightIndex >= len(arr) {
        smallerIndex = leftIndex
    } else if arr[leftIndex].Val <= arr[rightIndex].Val {
        smallerIndex = leftIndex
    } else {
        smallerIndex = rightIndex
    }
    if arr[i].Val > arr[smallerIndex].Val {
        arr[i], arr[smallerIndex] = arr[smallerIndex], arr[i]
        PercolateDown23(arr, smallerIndex)
    }
}

func PercolateUp23(arr []*ListNode, i int) {
    parentIndex := i / 2
    if parentIndex < 1 {
        return
    }
    if arr[i].Val < arr[parentIndex].Val {
        arr[i], arr[parentIndex] = arr[parentIndex], arr[i]
        PercolateUp23(arr, parentIndex)
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
    head := &ListNode{}
    tail := head
    mh := initMinHeap23()
    for _, list := range lists {
        if list != nil {
            mh.Insert23(list)
        }
    }
    for !mh.isEmpty() {
        node := mh.Pop()
        tail.Next = node
        tail = node
        if node.Next != nil {
            mh.Insert23(node.Next)
        }
    }
    return head.Next
}

Time: O(sum(list[i].length)log(list.length)) Space: O(list.length)

[haoyangxie]

code

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((a,b)->a.val - b.val);
        for (ListNode node : lists) {
            if (node != null)
            heap.add(node);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            head.next = cur;
            head = head.next;
            cur = cur.next;
            if (cur != null) {
                heap.add(cur);
            }
        }
        return dummy.next;
    }
}

complexity

Time: O(nlgn) Space: O(n)

[xi2And33]

class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(-1); ListNode head = dummy; PriorityQueue heap = new PriorityQueue((a,b)->a.val - b.val); for (ListNode node : lists) { if (node != null) heap.add(node); } while (!heap.isEmpty()) { ListNode cur = heap.poll(); head.next = cur; head = head.next; cur = cur.next; if (cur != null) { heap.add(cur); } } return dummy.next; } }

[ceramickitten]

Idea

分治，类似merge sort

Code

class Solution:
    def append_node(self, tail, node):
        next = node.next
        node.next = tail.next
        tail.next = node
        tail = node
        node = next
        return tail, node

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        if n == 0:
            return None
        if n == 1:
            return lists[0]
        m = n // 2
        head1 = self.mergeKLists(lists[:m])
        head2 = self.mergeKLists(lists[m:])
        tail = dummy_head = ListNode()
        while head1 and head2:
            if head1.val <= head2.val:
                tail, head1 = self.append_node(tail, head1)
            else:
                tail, head2 = self.append_node(tail, head2)
        while head1:
            tail, head1 = self.append_node(tail, head1)
        while head2:
            tail, head2 = self.append_node(tail, head2)
        return dummy_head.next

Complexity

n = lists.length, k = list.length

• Time: O(logn n k) 一共logn层，每层都需要处理n*k个节点
• Space: O(nlogn) 递归栈O(logn), 每层递归参数都申请了新的数组一共 O(nlogn)

[ashleyyma6]

Idea

• Divide and conquer. Merge two lists, and merge the merged lists, continue untill merged into one list.

Code

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 start, int end){
        if(start==end){
            return lists[start];
        }
        int mid = start+(end-start)/2;
        ListNode left = merge(lists, start, mid);
        ListNode right = merge(lists, mid+1, end);

        ListNode pre = new ListNode(0);
        ListNode head = pre;
        while(left != null && right != null){
            if(left.val<right.val){
                head.next = left;
                head = left;
                left = left.next;
            }else{
                head.next = right;
                head = right;
                right = right.next;
            }
        }
        if(left!= null){
            head.next = left;
        }else{
            head.next = right;
        }
        return pre.next;
    }
}

Complexity Analysis

• Time Complexity: O(nlog(m)) // n = # of linked list nodes, m = # of lists
• Space Complexity: O(1)

[User-Vannnn]

CODE 执行用时：88 ms, 在所有 Python3 提交中击败了45.14%的用户 内存消耗：17.9 MB, 在所有 Python3 提交中击败了85.60%的用户

# 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:
        # 合并两个有序链表可以看做是这个问题的子问题
        # 基本思路是:链表一直两两合并，最终会合并成一个链表
        k = len(lists)
        if k == 0:
            return None

        # 链表两两合并
        interval = 1
        while interval < k:
            # 落单的链表不用管，后面一定会找到配对的
            for i in range(0,k,interval*2):
                if i + interval < k:
                    lists[i] = self.mergeTwoLists(lists[i],lists[i+interval])
            # 更新步长
            interval *= 2

        return lists[0]

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 基本思路是:两个链表指针一次比较，小的往当前指针后面接，当一个链表为空时，把另一个链表接到后面即可
        cur = ListNode(0)
        head = cur
        while l1 != None or l2 != None:
            # 如果链表l1为空
            if l1 == None:
                cur.next = l2
                break
            # 如果链表l2为空
            if l2 == None:
                cur.next = l1
                break
            if l1.val <= l2.val:
                # cur.next = ListNode(l1.val)
                cur.next = l1
                l1 = l1.next
            else:
                # cur.next = ListNode(l2.val)
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        return head.next

[adamw-u]

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        d = {}
        for k in range(len(lists)):
            if lists[k]:
                d[k] = lists[k]
                heap.append((lists[k].val, k))
        heapq.heapify(heap)

        head = curr = ListNode()
        while heap:
            _, k = heapq.heappop(heap)
            curr.next = d[k]
            curr = curr.next
            d[k] = d[k].next
            if d[k]:
                heapq.heappush(heap, (d[k].val, k))
        curr.next = None
        return head.next

[zpc7]

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

        head = ListNode()
        p = head
        heap = []
        for i, pi in enumerate(lists):
            if pi:
                heapq.heappush(heap, (pi.val, i))
                lists[i] = lists[i].next

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

[Elon-Lau]

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

    int mid = lists.length / 2;
    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, j =0;i<lists.length;i++,j++){
        l2[j] = lists[i];
    }
    return mergeTwoLists(mergeKLists(l1), mergeKLists(l2));
}

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(l1, l2.next);
    }
    return head;
}

}

[aiweng1981]

思路

• 思路描述:感觉这个算hard吧！

代码

#代码
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)

[AtaraxyAdong]

class Solution { public ListNode mergeKLists(ListNode[] lists) {

    if (lists.length == 0) {
        return null;
    }

    ListNode dummyHead = new ListNode(0);
    ListNode curr = dummyHead;
    PriorityQueue<ListNode> pq = 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) {
            continue;
        }
        pq.add(list);
    }

    while (!pq.isEmpty()) {
        ListNode nextNode = pq.poll();
        curr.next = nextNode;
        curr = curr.next;
        if (nextNode.next != null) {
            pq.add(nextNode.next);
        }
    }
    return dummyHead.next;
}

}

[tian-pengfei]

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

    ListNode* mergeKLists(vector<ListNode*>& lists,int start,int end) {
        if(start>end)return nullptr;
        if(start==end)return lists[start];

        int mid = (start+end)/2;

        ListNode* left = mergeKLists(lists,start,mid);

        ListNode* right = mergeKLists(lists,mid+1,end);

        auto *node = new ListNode();

        auto *root = node;

        while (left&&right){
            if(left->val<right->val){
                node->next = left;
                left = left->next;
            }else{
                node->next=right;
                right=right->next;
            }
            node=node->next;
        }

        if(left)node->next =left;
        if(right)node->next = right;
        return root->next;

    }
};

[luckyoneday]

打卡

var mergeKLists = function (lists) {
    if (lists.length === 0) {
        return null
    }
    return mergeLists(lists, 0, lists.length - 1)
}

function mergeLists(lists, start, end) {
    if (start === end) {
        return lists[start]
    }
    const mid = start + ((end - start) >> 1)
    const leftList = mergeLists(lists, start, mid)
    const rightList = mergeLists(lists, mid + 1, end)

    return merge(leftList, rightList)
}

function merge(head1, head2) {
    let dmy = new ListNode(0)
    let p = dmy

    while (head1 && head2) {
        if (head1.val <= head2.val) {
            p.next = head1
            head1 = head1.next
        } else {
            p.next = head2
            head2 = head2.next
        }
        p = p.next
    }
    p.next = head1 ? head1 : head2

    return dmy.next
}

[uyplayer]

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

 // k个链表的合并，可以看做是k-1次，每两个链表之间的合并。
func mergeKLists(lists []*ListNode) *ListNode {
    var pre,cur *ListNode
    n := len(lists)
    for i:=0;i<n;i++{
            if i == 0 {
                pre = lists[i]
                continue 
            }
            cur = lists[i]
            // 这里变成两个链表的合并问题
            pre = merge(pre,cur)
    }
    return pre

}

// 合并两个单链表的算法
func merge(l1, l2 *ListNode) *ListNode {
    head := &ListNode{}
    cur := head
    for l1 != nil || l2 != nil {
        if 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
        } else if l1 != nil {
            cur.Next = l1
            break
        } else {
            cur.Next = l2
            break
        }
    }
    return head.Next
}

[zzzkaiNS]

打卡

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

[YANGZ001]

LeetCode Link

[Merge k Sorted Lists - LeetCode](https://leetcode.com/problems/merge-k-sorted-lists/)

Idea

Use priorityqueue of size k to store k nodes.

Each time, poll the listnode with least value.

Code

/**
 * 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;
        Queue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode k : lists) {
            if (k == null) continue;
            pq.offer(k);
        }
        ListNode dummy = new ListNode(1);
        ListNode p = dummy;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            if (cur.next != null) pq.offer(cur.next);
            p.next = cur;
            p = p.next;
        }
        return dummy.next;
    }
}

Complexity Analysis

Time Complexity

O(NlogK). For every poll and offer operation of priorityqueue, time complexity would be logK. And potentially there would be N-k operation.

Space Complexity

O(K)

[Hacker90]

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

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

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

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

时间复杂度：O(n∗logk) 空间复杂度：O(logk)

[ZhongXiangXiang]

思路

分治

代码

var mergeKLists = function(lists) {
    return merge(lists, 0, lists.length - 1)
};
function merge(lists, l, r) {
    if (l === r) return lists[l]
    if (l > r) return null
    const mid = (l + r) >> 1
    return mergeList(merge(lists, l, mid), merge(lists, mid + 1, r))
}

function mergeList(a, b) {
    if (!a) return b
    if (!b) return a
    let aNode = a
    let bNode = b
    let head = new ListNode('head')
    let tail = head
    while (aNode && bNode) {
        if (aNode.val <= bNode.val) {
            tail.next = aNode
            aNode = aNode.next
        } else {
            tail.next = bNode
            bNode = bNode.next
        }
        tail = tail.next
    }
    tail.next = aNode ? aNode : bNode
    return head.next
}

[hanschurer]

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: def merge(l, r): if l>r: return if l == r: return lists[l] mid = (l+r)//2 l1 = merge(l, mid) l2 = merge(mid+1, r) return mergeTwo(l1, l2) def mergeTwo(l1, l2): tail = dummmy = ListNode() 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 dummmy.next return merge(0, len(lists)-1)

[MaylingLin]

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

[acoada]

思路

分治

代码

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return
        if len(lists) == 1:
            return lists[0]

        res = ListNode()
        n = len(lists)
        return self.merge(lists, 0, n-1)

    def merge(self, lists, L, R):
        if L == R:
            return lists[L]

        mid = L + (R - L) // 2

        left = self.merge(lists, L, mid)
        right = self.merge(lists, mid+1, R)

        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, l1, l2):
        if not l2:
            return l1
        if not l1:
            return l2

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

复杂度

• Time: O(NlogN)
• Space: O(logN)

[chouqin99]

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

[andyyxw]

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  return lists
    .reduce((p, n) => {
      while (n) {
        p.push(n)
        n = n.next
      }
      return p
    }, [])
    .sort((a, b) => a.val - b.val)
    .reduceRight((p, n) => (n.next = p, n), null)
}

[SamLu-ECNU]

思路

明天再说。

代码

将上述过程转换为完整代码，可知：

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

复杂度

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

空间复杂度：$O(n*k)$

[neado]

/**
 * 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.length==0){
            return null;
        }
        //虚拟节点
        ListNode t=new ListNode(-1);
        ListNode p = t;
        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()){
            //取出最小值——即优先队列的 poll（）方法取出值，放入链表，
            ListNode node = pq.poll();
            p.next=node;
            if(node.next!=null){
                //将此链表下一节点加入队列
                pq.add(node.next);
            }
            //链表加入一个后向后移动
            p = p.next;
        }
        //返回头节点
        return t.next;
    }
}

[kernelSue]

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

          PriorityQueue<ListNode> heap = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
          for(int i = 0; i < lists.length; i++){
              if(lists[i] != null)
                  heap.offer(lists[i]);
          }
          if(heap.isEmpty())  return null;
          ListNode head = heap.peek();
          ListNode p = null;
          while(!heap.isEmpty()){
            ListNode x = heap.poll();
            if(x.next != null)  heap.offer(x.next);
            if(p != null)  p.next = x;
            p = x;
          }
          return head;
    }
}

复杂度

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

[youzhaing]

题目: 23. 合并K个升序链表

思路

分治，先分后合并（影响函数使用顺序）

python代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1, l2):
        if not l1: return l2
        if not l2: return l1
        prehead = ListNode(-1)
        cur = prehead 
        while l1 and l2:
            if l1.val >= l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1 
                l1 = l1.next 
            cur = cur.next 
        if l1: cur.next = l1
        if l2: cur.next = l2
        return prehead.next
    def merge(self, lists, l, r):
        if l == r: return lists[l]
        if l > r: return None 
        mid = (l + r)//2
        l1 = self.merge(lists, l, mid)
        l2 = self.merge(lists, mid + 1, r)
        return self.mergeTwoLists(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)

复杂度

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

[Irenia111]

var mergeKLists = function (lists) {
    function mergeTwoLists(l1, l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val<l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1,l2.next );
        return l2;
    }
    if(lists.length == 0) return null;

    while(lists.length > 1) {
        lists.push(mergeTwoLists(lists.shift(), lists.shift()));
    }
    return lists[0];
};

[maoting]

思路

归并

代码

const merge2List = (left, right) => {
    let dummyNode = new ListNode();
    let cur = dummyNode;
    while(left && right) {
        if (left.val <= right.val) {
            cur.next = left;
            left = left.next;
            cur = cur.next;
        }
        else {
            cur.next = right;
            right = right.next;
            cur = cur.next;
        }
    }
    cur.next = left ? left : right;
    return dummyNode.next;
}
function mergeLists(lists, start, end) {
    if (start === end) {
        return lists[start]
    }
    const mid = start + ((end - start) >> 1)
    const leftList = mergeLists(lists, start, mid)
    const rightList = mergeLists(lists, mid + 1, end)

    return merge2List(leftList, rightList)
}
var mergeKLists = function(lists) {
    if (lists.length === 0) {
        return null
    }
    return mergeLists(lists, 0, lists.length - 1);
};

复杂度

时间复杂度：O(n∗logk) 空间复杂度：O(logk)