【力扣23】合并k个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

实现代码

方式一

基于优先级队列的特性，先将所有链表添加到优先级队列中，那么就会给每个链表的第一个节点进行排序，队列第一个就是头节点最小的链表，取出第一个节点添加到新链表，再移至链表下一个节点，重新放入优先级队列，重复移除放入的操作，最终新链表就是已排序的链表

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 合并k个排序链表
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 */
public class Demo {

  /**
     * 优先级队列方式
     * @param lists
     * @return
     */
  public ListNode mergeKLists(ListNode[] lists) {

    PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
    if (lists.length == 0) {
      return null;
    }
    ListNode listNode = new ListNode(-1), p;
    p = listNode;
    for (ListNode node : lists) {
      if (node == null) {
        continue;
      }
      priorityQueue.add(node);
    }
    while (!priorityQueue.isEmpty()) {
      ListNode poll = priorityQueue.poll();
      p.next = poll;
      p = p.next;
      ListNode next = poll.next;
      if (next != null) {
        priorityQueue.add(next);
      }
    }
    return listNode.next;
  }

  static class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}

方式二

双指针方式，每次将合并后的链表与下一条链表进行合并

/**
 * 合并k个排序链表
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 */
public class Demo1 {

  /**
     * 双指针方式
     *
     * @param lists
     * @return
     */
  public ListNode mergeKLists(ListNode[] lists) {

    ListNode tmp = null;
    for (int i = 0; i < lists.length; i++) {
      // 每次将tmp链表与下一个链表进行合并
      tmp = mergeTwoListNode(tmp, lists[i]);
    }
    return tmp;
  }

  private ListNode mergeTwoListNode(ListNode one, ListNode two) {

    ListNode tmp = new ListNode(-1), p;
    p = tmp;
    ListNode p1 = one, p2 = two;
    while (p1 != null && p2 != null) {

      if (p1.val < p2.val) {

        p.next = p1;
        p1 = p1.next;
      } else {
        p.next = p2;
        p2 = p2.next;
      }
      p = p.next;
    }
    if (p1 != null) {
      p.next = p1;
    }
    if (p2 != null) {
      p.next = p2;
    }
    return tmp.next;
  }

  static class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {

      this.val = val;
      this.next = next;
    }
  }
}

方式三

分治算法，通过将k个链表进行二分，一直分到不能再分，再进行合并

/**
 * 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;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {

        // 一直分到left与right相等才返回
        if (left == right) {
            return lists[left];
        }
        // 这种求中间索引值的方法和(left + right) / 2 是等价的，这样写是为了防止整数溢出风险
        // 如果right和left的值都非常大，相加可能会超过int的最大值
        int mid = left + (right - left) / 2;
        // 处理左边
        ListNode leftListNode = merge(lists, left, mid);
        // 处理右边
        ListNode rightListNode = merge(lists, mid + 1, right);
        // 左右链表进行合并
        return mergeTwoLists(leftListNode, rightListNode);
    }

    /**
     * 合并两个链表
     * @param listNode1 链表1
     * @param listNode2 链表2
     * @return 合并链表
     */
    private ListNode mergeTwoLists(ListNode listNode1, ListNode listNode2) {

        // 定义链表索引
        ListNode p1 = listNode1, p2 = listNode2;
        // 虚拟节点
        ListNode p = new ListNode(-1), pp = p;
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                pp.next = p1;
                p1 = p1.next;
            } else {
                pp.next = p2;
                p2 = p2.next;
            }
            pp = pp.next;
        }
        if (p1 != null) {
            pp.next = p1;
        }
        if (p2 != null) {
            pp.next = p2;
        }
        return p.next;
    }
}