前言

本文主要介紹如何將多個小的升序鏈表合并一個大的升序鏈表。

需求描述

給出K個升序鏈接，要求把這K個升序鏈表合并成一個，并且這個鏈表也是升序的。

例如：A = [1,5,6]， B = [2,3,8], C = [4,4,9] 將這3個鏈表合并成一個鏈表D，合并后D = [1,2,3,4,4,5,6,8,9]，并且將D的第一個節(jié)點(diǎn)返回。

思路解析

我們可以采用優(yōu)先級隊列來實(shí)現(xiàn)，先把每個鏈表的頭結(jié)點(diǎn)放到一個優(yōu)先級隊列里，優(yōu)先級隊列也叫小根堆。

在放小根堆的時候，誰小就把誰放在最上面。需要注意的是，我們放入的時候，放入的是節(jié)點(diǎn)，所以通過這個節(jié)點(diǎn)是可以訪問整個鏈表的。

我們看下處理過程：

• 首先把每個鏈接的頭結(jié)點(diǎn)放入小根堆中：1，2，4。
• 首先彈出最小的值：1。
• 把1節(jié)點(diǎn)的下一個節(jié)點(diǎn)5放入小根堆中，此時小根堆會自動調(diào)整順序，此時為：2, 4, 5。
• 將2節(jié)點(diǎn)彈出，讓1節(jié)點(diǎn)的next指針指向2節(jié)點(diǎn)，并且將2節(jié)點(diǎn)的下一個節(jié)點(diǎn)6放入小根堆，此時已彈出的節(jié)點(diǎn)為 1,2，而小根堆為4, 5, 6。
• 將4節(jié)點(diǎn)彈出，讓2節(jié)點(diǎn)的next指針指向4節(jié)點(diǎn)，并且將4節(jié)點(diǎn)的下一個節(jié)點(diǎn)4放入小根堆中，此時已彈出的節(jié)點(diǎn)為1,2,4，而小根堆為4, 5, 6。
• 依此類推，每彈出一個節(jié)點(diǎn)，拼接在已彈出節(jié)點(diǎn)的后面，并將彈出節(jié)點(diǎn)的下一個節(jié)點(diǎn)放入小根堆中，直到小根堆中所有的元素全部彈出。

好了，現(xiàn)在整體思路有了，但是現(xiàn)在是不是有個疑問？我們在做算法時，使用到了優(yōu)先隊列，那么我們可以使用系統(tǒng)自帶的優(yōu)先隊列嗎？

個人感覺，如果是面試時，這個系統(tǒng)自帶的類只是題目中很小的一部分，比如上面的題目，主要考察的是如何實(shí)現(xiàn)這個過程，而不是考察如何實(shí)現(xiàn)優(yōu)先隊列的，如果沒有特殊要求不讓使用的話，是可以使用的。當(dāng)然，如果考察是要實(shí)現(xiàn)一個優(yōu)先隊列，我要是直接new一個PriorityQueue，我估計面試官會一巴掌把我拍出來。

代碼實(shí)現(xiàn)

鏈表節(jié)點(diǎn)定義如下：

public class ListNode {
   public int val;
   public ListNode next;
}

因?yàn)槭切「?，需要一個排序算法，所以定義一個比較器如下：

public class ListNodeComparator implements Comparator<ListNode> {
   @Override
   public int compare(ListNode o1, ListNode o2) {
      return o1.val - o2.val; 
   }
}

合并鏈接：

public ListNode mergeKLists(ListNode[] lists) {
   if (lists == null) {
      return null;
   }
   PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
   for (int i = 0; i < lists.length; i++) {
      if (lists[i] != null) {
         heap.add(lists[i]);
      }
   }
   if (heap.isEmpty()) {
      return null;
   }
   ListNode head = heap.poll();
   ListNode pre = head;
   if (pre.next != null) {
      heap.add(pre.next);
   }
   while (!heap.isEmpty()) {
      ListNode cur = heap.poll();
      pre.next = cur;
      pre = cur;
      if (cur.next != null) {
         heap.add(cur.next);
      }
   }
   return head;
}

這個方法參數(shù)lists代表要傳進(jìn)來多少個鏈表，方法合并多個鏈表后，返回鏈表的第一個節(jié)點(diǎn)。

時間復(fù)雜度

假設(shè)有M個鏈表，M個鏈表的總節(jié)點(diǎn)個數(shù)為N。此時，對于小根堆來說，他的規(guī)模大小為M，則對于小根堆來說他的操作時間復(fù)雜度為O(logM)，一共有N個節(jié)點(diǎn)，所以時間復(fù)雜度為O(N*logM)。

總結(jié)

本文主要介紹如何將多個小的升序鏈表合并一個大的升序鏈表，介紹了實(shí)現(xiàn)這個功能的思路分析，使用優(yōu)先隊列自動排序的特性實(shí)現(xiàn)了這個功能，當(dāng)然這里我們使用的是系統(tǒng)自帶的優(yōu)先隊列，其實(shí)也可以自己實(shí)現(xiàn)一個，個人感覺沒太必要，就先偷個懶 。更多相關(guān)Java 合并升序鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

到此這篇關(guān)于Java實(shí)現(xiàn)合并多個升序鏈表的文章就介紹到這了,更多相關(guān)Java 合并升序鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論