BM5 合并k个已排序的链表

描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数满足 0≤n≤10^5 ，链表个数满足1≤k≤10^5 ，每个链表的长度满足1≤len≤200 ，每个节点的值满足 |val| <= 1000

要求：时间复杂度 O(nlogk)

输入：
[{1,2},{1,4,5},{6}]
返回值：
{1,1,2,4,5,6}

辅助数组

解题思路
主要采用将列表中的链表结点值遍历存储到辅助数组中，再对数组进行排序，根据排序后的数组元素一次构建新链表
1、遍历列表，分别将每一个链表的元素值存储到数组tmp中
2、对tmp进行排序
3、依次遍历数组元素创新新链表

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        # 将所有链表元素存放到list中，排序后再转换为链表
        tmp = []
        for head in lists:
            while head:
                # 将链表结点存放到tmp中
                tmp.append(head.val)
                head = head.next
        if not tmp:
            return None
        # tmp进行排序
        tmp.sort()
        res = ListNode(-1)
        cur = res
        # 根据tmp生成新的链表
        for i in range(len(tmp)):
            cur.next = ListNode(tmp[i])
            cur = cur.next
        return res.next

顺序合并

解题思路
1、将k个链表配对并将同一对中的链表进行合并（采用顺序合并的方法）
2、第一轮合并后，k个链表合并成了 k/2 个链表，平均长度 2n/k ，然后是 k/4、k/8…等等
3、重复这一过程，知道获取最终的有序链表

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayListlists) {
        // 采用分治进行合并链表
        return mergeList( lists , 0 , lists.size() - 1 );
    }
    // 分治进行链表两两合并
    public ListNode mergeList(ArrayListlists , int L ,int R){
        
        if(L == R){
            return lists.get(L);
        }
        if(L > R){
            return null;
        }
        
        int mid = L + ((R - L) >> 1);
        return merge( mergeList(lists,L,mid) , mergeList(lists,mid+1,R));
    }
    
    // 合并两个链表，对比合并
    public ListNode merge(ListNode l1 , ListNode l2){
        
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
        
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        
        while( l1 != null && l2 != null){
            
            if(l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 == null ? l2 : l1); return dummy.next; } }

优先队列

解题思路
使用优先队列去存储所有链表。按照链表头结点值，进行从小到大的排序，最小的头结点的链表在堆顶。
1、每次将堆顶的链表取出
2、将头结点从取出的链表上去除，并插在所需目标链表的尾部。
3、将取出的链表放回堆中。若链表为null，则不放回。
重复1，2，3过程，直到堆为空，循环终止。

import heapq

class Solution:
    def mergeKLists(self , lists ):
        # write code here
        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

self

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        List<Integer> tmp = lists.stream().map(v -> {
				List<Integer> temp = new ArrayList<>();
				while (v != null) {
					temp.add(v.val);
					v = v.next;
				}
				return temp;
			})
			.flatMap(List::stream)
			.collect(Collectors.toList());
		Collections.sort(tmp);
		ListNode result = new ListNode(-1);
		ListNode p = result;
		for (Integer integer : tmp) {
			p.next = new ListNode(integer);
			p = p.next;
		}
		return result.next;
    }
}