阿裡巴巴面試算法題——合并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;
  }
}