原題目鏈接：23. 合并K個升序鏈表
做題思路
- 先了解如何合并兩個升序鏈表
1.1 首先設定一個哨兵節點prevHead，這個節點的目的是為了方便我們最后找到合并后的鏈表的頭結點，設定為-1，由于鏈表是有序，如果插入的話，肯定在頭部， - 設定一個prev指標，我們只需要維護它的next屬性，這個指標的目的是為了串聯兩條鏈表，
- 比較l1和l2的大小，l1和l2就是兩條鏈表
3.1 如果l1的值小于等于l2的值，上一個節點的next指向l1，l1指向下一個節點
3.2 如果l1的值大于l2的值，上一個節點的next指向l2，l2指向下一個節點
我們以，l1鏈表1->3->6->7，l2鏈表1->2->4->5->9，為例子進行影片演示
點擊這里在B站看影片演示喔
廢話不多說，直接上代碼
private ListNode mergeTwoLists(ListNode l1,ListNode l2){
if(l1 == null || l2 == null){ //如果一條鏈表為空，則回傳不空的鏈表
return l1 == null ? l2 : l1;
}
//準備一個哨兵節點，目的是為了方便回傳鏈表頭結點
ListNode preHead = new ListNode(-1);
//維護這個prev節點，為了可以把兩條鏈表的元素串聯起來
ListNode prev = preHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){ //l1節點元素的值小于等于l2節點元素的值
prev.next = l1;
l1 = l1.next;
}else{ //l1節點元素的值大于l2節點元素的值
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
//在兩條鏈表比較完之后，肯定有一條鏈表還有剩下的節點沒有比較，由于是有序的，可以直接放入后面
prev.next = l1 == null ? l2 : l1;
//回傳哨兵節點，找到鏈表頭結點
return preHead.next;
}
在了解完如何合并兩條升序鏈表之后，依次類推，可以通過不斷地呼叫這個mergeTwoLists方法，去實作合并K條升序鏈表，
設定一個變數ans來保存已經合并后的鏈表
廢話不多說，直接上代碼
public ListNode mergeKLists(ListNode[] lists) {
//用一個變數ans來保存已經合并后的鏈表
ListNode ans = null;
for(int i = 0; i < lists.length; i++){
//合并兩個有序鏈表
ans = mergeTwoLists(ans,lists[i]);
}
return ans;
}
所以最終的代碼就是
public ListNode mergeKLists(ListNode[] lists) {
//用一個變數ans來保存已經合并后的鏈表
ListNode ans = null;
for(int i = 0; i < lists.length; i++){
//合并兩個有序鏈表
ans = mergeTwoLists(ans,lists[i]);
}
return ans;
}
private ListNode mergeTwoLists(ListNode l1,ListNode l2){
if(l1 == null || l2 == null){ //如果一條鏈表為空，則回傳不空的鏈表
return l1 == null ? l2 : l1;
}
//準備一個哨兵節點，目的是為了方便回傳鏈表頭結點
ListNode preHead = new ListNode(-1);
//維護這個prev節點，為了可以把兩條鏈表的元素串聯起來
ListNode prev = preHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){ //l1節點元素的值小于等于l2節點元素的值
prev.next = l1;
l1 = l1.next;
}else{ //l1節點元素的值大于l2節點元素的值
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
//在兩條鏈表比較完之后，肯定有一條鏈表還有剩下的節點沒有比較，由于是有序的，可以直接放入后面
prev.next = l1 == null ? l2 : l1;
//回傳哨兵節點，找到鏈表頭結點
return preHead.next;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/250258.html
標籤：其他