【Day 69 】2023-01-08 - 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

[zjsuper]

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]) else: mid = len(lists)//2 return self.merge2(self.mergeKLists(lists[:mid]),self.mergeKLists(lists[mid:])) def merge2(self,l,r): ans = ListNode(0) head = ans while l and r: if l.val<r.val: ans.next = l l = l.next ans = ans.next else: ans.next = r ans = ans.next r = r.next if l: ans.next = l if r: ans.next = r return head.next

[heng518]

class Solution { public: struct compare { bool operator() (ListNode a, ListNode b){ return a->val > b->val; } };

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, compare> q;
    ListNode* dummy = new ListNode(-1);
    ListNode* current_head = dummy;
    for(int i = 0; i < lists.size(); i++)
    {
        if(lists[i] != NULL)
        {
            q.push(lists[i]);
        }
    }

    while(!q.empty())
    {
        current_head->next = q.top();
        if(q.top()->next)
            q.push(q.top()->next);
        q.pop();
        current_head = current_head->next;
    }
    return dummy->next;
}

};

[snmyj]

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) {
       for(int k=lists.size();k>1;k=(k+1)/2){
        for(int i=0;i<k/2;i++){
         list[i]=mergetwolists(lists[i],lists[k-1-i])   
        }
    }
        return lists[0];

    }
};

[JancerWu]

思路

归并排序分治的思想，把左边归并，把右边归并，然后再合起来

代码

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

    public ListNode mergeSort(ListNode[] lists, int start, int end) {
        if (start + 1 == end) return lists[start];
        int mid = (start + end) / 2;
        ListNode left = mergeSort(lists, start, mid);
        ListNode right = mergeSort(lists, mid, end);
        return merge(left, right);
    }

    public ListNode merge(ListNode left, ListNode right) {
        ListNode p = left, q = right;
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (p != null && q != null) {
            if (p.val < q.val) {
                tail.next = p;
                p = p.next;
            } else {
                tail.next = q;
                q = q.next;
            }
            tail = tail.next;
        }
        tail.next = p == null ? q : p;
        return dummy.next;
    }
}

[JancerWu]

思路

K指针

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        int n = lists.length;
        ListNode[] points = new ListNode[n];
        for (int i = 0; i < n; i++) points[i] = lists[i];
        while (true) {
            int minV = Integer.MAX_VALUE, id = -1;
            for (int i = 0; i < n; i++) {
                if (points[i] != null && points[i].val < minV) {
                    minV = points[i].val;
                    id = i;
                }
            }
            if (id == -1) break;
            tail.next = points[id];
            tail = tail.next;
            points[id] = points[id].next;
        }
        return dummy.next;
    }
}

[klspta]

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        ListNode res = new ListNode();
        ListNode cur = res;

        for(ListNode listNode : lists){
            if(listNode != null){
                q.offer(listNode);
            }
        }

        while(!q.isEmpty()){
            ListNode tmp = q.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null){
                q.offer(tmp.next);
            }
        }

        return res.next;
    }

[buer1121]

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

    if not lists:return

    def merge2Lists(l1,l2):#两有序链表合并
        if not l1:return l2
        if not l2:return l1
        dummpy=ListNode(-1)
        temp=dummpy
        while l1 and l2:
            if l1.val<l2.val:
                temp.next=l1
                l1=l1.next
            else:
                temp.next=l2
                l2=l2.next
            temp=temp.next
        if l1:
            temp.next=l1
        if l2:
            temp.next=l2

        return dummpy.next

    def helper(l,r):#二分法 使所有链表两两合并
        if l==r:return lists[l]
        n=len(lists)
        mid=(l+r)//2

        l1=helper(l,mid)
        l2=helper(mid+1,r)

        return merge2Lists(l1,l2)

    return helper(0,len(lists)-1)

[Abby-xu]

思路

Heap挨个存储，最后pop建立一个有序LL

代码

import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        ListNode.__lt__ = lambda self, other: self.val < other.val
        h = []
        head = tail = ListNode(0)
        for i in lists:
            if i: heapq.heappush(h, i)
        while h:
            node = heapq.heappop(h)
            tail.next = node
            tail = tail.next
            if node.next: heapq.heappush(h, node.next)
        return head.next 

复杂度

O(nlogK) / O(k)

[bookyue]

code

1. dive and conquer
2. min heap

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

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

    private ListNode mergeKLists(ListNode[] lists, int begin, int end) {
        if (begin >= end) return lists[begin];

        int mid = (begin + end) >>> 1;
        ListNode left = mergeKLists(lists, begin, mid);
        ListNode right = mergeKLists(lists, mid + 1, end);
        return mergeList(left, right);
    }

    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode dummny = new ListNode(-1);
        var cur = dummny;

        while (left != null && right != null) {
            if (right.val < left.val) {
                cur.next = right;
                right = right.next;
            } else {
                cur.next = left;
                left = left.next;
            }

            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummny.next;
    }

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

[FlipN9]

/**
    Approach 1: MinHeap      
    TC: O(Nlogk)    O(logk) for every pop and insertion to pq
    SC: O(k) for pq ==> O(1)
*/
class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(Integer.compare(a.val, b.val)));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null) 
                pq.add(head);
        }
        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            // 将node.next重新加入pq
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

/**
    Approach 2: Divide & Conquer
    TC: O(Nlogk)    SC: O(1)
*/
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeHelper(lists, 0, lists.length - 1);
    }

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

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

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if (l1 != null) {
            p.next = l1;
        } else {
            p.next = l2;
        }
        return dummy.next;
    }
}

[mayloveless]

思路

分治，俩俩合并，最后合成一个。

代码

/**
 * 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) {
    if(!lists.length) return null;
    return helper(lists, 0, lists.length - 1)
};

function helper(lists, left, right) {
    if (left >= right) {
        return lists[left]
    }
    const mid = Math.floor((left + right) / 2)
    const l1 = helper(lists, left, mid)
    const l2 = helper(lists, mid + 1, right)
    return mergeTwoLists(l1, l2)
}
function mergeTwoLists (l1, l2) {
    let prehead = new ListNode(-1);

    let prev = prehead;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    prev.next = l1 == null ? l2 : l1;
    return prehead.next;
}

复杂度

时间：O(kn*logk) 空间 ：O（logk）栈空间

[zywang0]

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
        ListNode res = new ListNode();
        ListNode cur = res;

        for(ListNode listNode : lists){
            if(listNode != null){
                q.offer(listNode);
            }
        }

        while(!q.isEmpty()){
            ListNode tmp = q.poll();
            cur.next = tmp;
            cur = cur.next;
            if(tmp.next != null){
                q.offer(tmp.next);
            }
        }

        return res.next;
    }

[Elsa-zhang]

# 合并 K 个排序链表
''' 合并 k 个排序链表，返回合并后的排序链表 请分析和描述算法的复杂度
    分治
    时间复杂度 O(kn*logk)
'''

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

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

    def merge2Lists(self, list1: ListNode, list2: ListNode):
        res = ListNode(0)
        n1, n2, n3 = list1, list2, res
        while n1 and n2:
            if n1.val < n2.val:
                n3.next = ListNode(n1.val)
                n1 = n1.next
            else:
                n3.next = ListNode(n2.val)
                n2 = n2.next
            n3 = n3.next

        while n1:
            n3.next = ListNode(n1.val)
            n1 = n1.next
            n3 = n3.next

        while n2:
            n3.next = ListNode(n2.val)
            n2 = n2.next
            n3 = n3.next

        return res.next

lists = [[1,4,5],[1,3,4],[2,6]]
solution = Solution()
ans = solution.mergeKLists(lists)
print(ans)

[A-pricity]

/**
 * 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) {
    function transform(l, arr) {
        while(l) {
            arr.push(l.val);
            l = l.next;
        }
    }

    let arr = [];
    let res = new ListNode(null);

    lists.map(item => transform(item, arr));
    arr.sort((a, b) => a - b);
    for (let i = arr.length - 1; i >= 0; i--) {
        let temp = new ListNode(null);
        res.val = arr[i];
        temp.next = res;
        res = temp;
    }

    return res.next;
};

[tiandao043]

/**
 * 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 *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
    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(kn*logk) O(logk)

/**
 * 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:
    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;
    }
};

[RestlessBreeze]

code

class Solution {
public:
    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;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

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

[paopaohua]

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

[Jetery]

23. 合并K个升序链表

思路 1 小根堆

将所有链表头节点指针加入小根堆, 每次在傀儡节点后 通过移动tail指针, 添加堆顶元素cur, 如果cur后含有节点, 则加入堆中

代码 (cpp)

/**
 * 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:
    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;
    }
};

复杂度分析

• 时间复杂度：O(nlogk)

• 空间复杂度：O(k)

[Alexno1no2]

# 利用堆的数据结构

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq #调用堆
        minHeap = []
        for listi in lists: 
            while listi:
                heapq.heappush(minHeap, listi.val) #把listi中的数据逐个加到堆中
                listi = listi.next
        head = ListNode(0) #构造虚节点
        p = head
        while minHeap:
            p.next = ListNode(heapq.heappop(minHeap)) #依次弹出最小堆的数据
            p = p.next
        return head.next 

[whoam-challenge]

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

[MaylingLin]

思路

---

用一个小顶堆保存每个链表中的最小节点，每次将值最小的节点出堆，加入新的有序链表，并将这个节点的后一个节点入堆，直到堆中没有节点。

代码

class Solution:
      def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
         h = []
         for idx, node in enumerate(lists):
           if node: h.append((node.val, idx, node))
               heapq.heapify(h)
               p = new_head = ListNode()
               while h:
                  _, idx,node = heapq.heappop(h)
                  p.next = node
                  p = p.next
                  if node.next:
                      heapq.heappush(h, (node.next.val, idx,node.next))
      return new_head.next

复杂度

---

• Time: $O(n * logk)$
• Space: $O(logk)$

[Ryanbaiyansong]

# 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]:
        # 多路归并
        dummy = ListNode(0)
        cur = dummy 
        minHeap = [] # pair(value, index)
        for i, h in enumerate(lists):
            if h:
                heappush(minHeap, (lists[i].val, i))

        while minHeap:
            v, idx = heappop(minHeap)
            node = ListNode(v)
            cur.next = node 
            cur = cur.next 
            if lists[idx].next:
                lists[idx] = lists[idx].next
                heappush(minHeap, (lists[idx].val, idx))

        return dummy.next