前言

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

需求描述

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

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

思路解析

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

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

我們看下處理過程：

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

好了，現(xiàn)在整體思路有了，但是現(xiàn)在是不是有個(gè)疑問？我們?cè)谧鏊惴〞r(shí)，使用到了優(yōu)先隊(duì)列，那么我們可以使用系統(tǒng)自帶的優(yōu)先隊(duì)列嗎？

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

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

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

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

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

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;
}

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

時(shí)間復(fù)雜度

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

總結(jié)

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

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