維護(hù)不易，點贊再看，感謝支持

合并K個升序鏈表

題目描述

給你一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。
請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數(shù)組如下：
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

示例 2：

輸入：lists = []
輸出：[]

示例 3：

輸入：lists = [[]]
輸出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的總和不超過 10^4

分析
這題合并多個鏈表，可以遍歷當(dāng)前有效的(不為null)鏈表頭找到最小的那個，逐一插入到新的鏈表中。也可以從前往后兩兩合并鏈表，使用上面合并兩個有序鏈表的方法。但是這兩種需要比較的次數(shù)。時間復(fù)雜度都為O(n*k)其中n為節(jié)點總個數(shù)，K為鏈表個數(shù)。

進(jìn)行優(yōu)化主要有兩種具體實現(xiàn)思路 ，一種就是利用一種排序每次找到最小的節(jié)點，而這種更適合堆排序動態(tài)維護(hù)。另一種就是利用類似歸并的思想。將兩兩歸并，最終歸并為一個鏈表。從效率上看每個比較次數(shù)本來從k次由歸并變成了log k，所以時間復(fù)雜度為O(nlogk);而合并具體操作也有直接迭代和遞歸兩種方式，這里就使用迭代的方式。

實現(xiàn)代碼為：

public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0)return null;if(lists.length==1)return lists[0];List<ListNode>nodes1=new ArrayList<ListNode>();List<ListNode>nodes2=new ArrayList<ListNode>();int i=0;//歸并for(;i<lists.length-1;i+=2){nodes1.add(mergeTwoLists(lists[i],lists[i+1]));}if(i==lists.length-1)nodes1.add(lists[i]);while (true) {for(i=0;i<nodes1.size()-1;i+=2){nodes2.add(mergeTwoLists(nodes1.get(i), nodes1.get(i+1)));}if(i==nodes1.size()-1) nodes2.add(nodes1.get(nodes1.size()-1));nodes1.clear();nodes1.addAll(nodes2);nodes2.clear();if(nodes1.size()==1)return nodes1.get(0);} }public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1==null)return l2;if(l2==null)return l1;if(l1.val>l2.val)//l1更小{ListNode team=l1;l1=l2;l2=team;}ListNode value=l1;while (l2!=null) {if(l1.next==null){l1.next=l2;break;}else if (l1.next.val<l2.val) {l1=l1.next;}else {ListNode node=l1.next;l1=l1.next=l2;l2=node;//l1=l1.next;}}return value; }

當(dāng)然這樣編寫對數(shù)組的利用比較差，每次重新賦值浪費一定效率，可以直接復(fù)用數(shù)組每次兩兩合并的時候賦值到對應(yīng)位置。具體代碼為：

public ListNode mergeKLists(ListNode[] lists) {if(lists.length==0)return null;if(lists.length==1)return lists[0];int k=lists.length-1;while (k>0) {int i;for(i=0;i<k;i+=2){lists[i/2]=mergeTwoLists(lists[i], lists[i+1]);}if(i==k){lists[i/2]=lists[i];k=(k+1)/2; }else{k/=2;}} return lists[0];}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {//此處省略}

兩兩交換鏈表中的節(jié)點

分析：
本題的要求就是交換奇偶節(jié)點。不能直接交換值也就意味不能直接賦值要通過鏈表插入刪除來實現(xiàn)。而具體的流程也很簡單：

具體實現(xiàn)代碼為：

public ListNode swapPairs(ListNode head) {if(head==null)return head;ListNode value=new ListNode(0);value.next=head;ListNode team=value;ListNode first;ListNode second;while (team!=null&&team.next!=null) {if(team.next.next==null)return value.next;first=team.next;second=team.next.next;team.next=second;first.next=second.next;second.next=first;team=first;//team=team.next.next}return value.next;}

結(jié)語

原創(chuàng)不易，bigsai請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在平臺創(chuàng)作的源源動力。

微信搜索「bigsai」，關(guān)注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術(shù)。加我還可拉你進(jìn)力扣打卡群一起打卡LeetCode。

記得關(guān)注、咱們下次再見！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 23合并K个升序链表24两两交换链表中的节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。