阿里巴巴面试算法题——合并n个升序链表,so easy~

题目

将n个升序链表合并为一个升序链表

分析

1. 所有待合并链表都为升序
2. 比较每个链表当前的最小节点，找到minNode（所有链表中最小节点）
3. 将minNode加入合并的链表
4. 用minNode的下一个节点继续比较
5. 重复步骤2 ~ 步骤4，直至遍历所有节点

题解

• 比较node1和node2

  

• 将较小的node1添加到mergedLinkedList中，比较node2和node3

  

• 将较小的node2添加到mergedLinkedList中，比较node3和node4

  

• 将较小的node3添加到mergedLinkedList中，将node4添加到mergedLinkedList中

  

public class MergeListsDemo {
  public ListNode mergeLists(ListNode[] lists) {
    if (lists == null) return null;
    // 创建最小堆，用于找到当前所有链表中最小的节点
    PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
    // 将待merge链表中的最小节点添加到最小堆中
    for (ListNode node : lists) if (node != null) queue.offer(node);
    // 为方便编码，创建伪节点
    ListNode dummy = new ListNode();
    ListNode node = dummy;
    while (!queue.isEmpty()) {
      // 找到当前最小节点
      ListNode minNode = queue.poll();
      // 将minNode添加到mergedLinkedList中
      node.next = minNode;
      // 指向mergedLinkedList的尾部节点
      node = node.next;
      // 将minNode的next节点加入最小堆中
      if (node.next != null) queue.offer(node.next);
    }
    return dummy.next;
  }
}

class ListNode {
  int val;
  ListNode next;

  ListNode() {}

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

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