Java實現合併多個升序連結串列

2023-11-22 14:00:31

前言

本文主要介紹如何將多個小的升序連結串列合併一個大的升序連結串列。

需求描述

給出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的第一個節點返回。

思路解析

我們可以採用優先順序佇列來實現，先把每個連結串列的頭結點放到一個優先順序佇列裡，優先順序佇列也叫小根堆。

在放小根堆的時候，誰小就把誰放在最上面。需要注意的是，我們放入的時候，放入的是節點，所以通過這個節點是可以存取整個連結串列的。

我們看下處理過程：

首先把每個連結的頭結點放入小根堆中：1，2，4。
首先彈出最小的值：1。
把1節點的下一個節點5放入小根堆中，此時小根堆會自動調整順序，此時為：2, 4, 5。
將2節點彈出，讓1節點的next指標指向2節點，並且將2節點的下一個節點6放入小根堆，此時已彈出的節點為 1,2，而小根堆為4, 5, 6。
將4節點彈出，讓2節點的next指標指向4節點，並且將4節點的下一個節點4放入小根堆中，此時已彈出的節點為1,2,4，而小根堆為4, 5, 6。
依此類推，每彈出一個節點，拼接在已彈出節點的後面，並將彈出節點的下一個節點放入小根堆中，直到小根堆中所有的元素全部彈出。

好了，現在整體思路有了，但是現在是不是有個疑問？我們在做演演算法時，使用到了優先佇列，那麼我們可以使用系統自帶的優先佇列嗎？

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

程式碼實現

連結串列節點定義如下：

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

因為是小根堆，需要一個排序演演算法，所以定義一個比較器如下：

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

這個方法引數lists代表要傳進來多少個連結串列，方法合併多個連結串列後，返回連結串列的第一個節點。

時間複雜度

假設有M個連結串列，M個連結串列的總節點個數為N。此時，對於小根堆來說，他的規模大小為M，則對於小根堆來說他的操作時間複雜度為O(logM)，一共有N個節點，所以時間複雜度為O(N*logM)。

總結

本文主要介紹如何將多個小的升序連結串列合併一個大的升序連結串列，介紹了實現這個功能的思路分析，使用優先佇列自動排序的特性實現了這個功能，當然這裡我們使用的是系統自帶的優先佇列，其實也可以自己實現一個，個人感覺沒太必要，就先偷個懶。更多相關Java 合併升序連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

到此這篇關於Java實現合併多個升序連結串列的文章就介紹到這了,更多相關Java 合併升序連結串列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java實現合併多個升序連結串列

目錄

前言

需求描述

思路解析

程式碼實現

時間複雜度

總結

熱門文章