資訊專欄INFORMATION COLUMN
摘要：問題描述輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
1.問題描述
輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
2.思路方法1:非遞歸方法
根據(jù)題目這個很類似排序中的外排過程,兩個數(shù)組分別排好序,然后再把他們整體進行排序.所以這道題思想很簡單,就是用兩個變量分別遍歷兩個鏈表.比較遍歷到的兩個節(jié)點的值,小的節(jié)點就斷開與后面的連接,連到遍歷到的另一個節(jié)點上,同時讓小的節(jié)點向后移動一位,大節(jié)點位置不變,所以這里需要一個變量來記錄值較小的節(jié)點后面一個節(jié)點,保證斷開與后面的連接后可以獲得后面的節(jié)點.這樣執(zhí)行循環(huán)操作,直到一個鏈表循環(huán)到最后停止.就會把兩個鏈表合成一個有序的新鏈表.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) //判斷鏈表1是否為null,如果為null,直接返回鏈表2.
return list2;
else if(list2 == null) //判斷鏈表2是否為null.
return list1;
ListNode pNode1 = list1; //記錄鏈表1的頭節(jié)點,因為要返回新的鏈表,所以最后比較一下返回值較小的頭節(jié)點
ListNode pNode2 = list2; //記錄鏈表2的頭節(jié)點
ListNode next = null; //小節(jié)點斷開與后面的連接時用于記錄小節(jié)點后面的一個節(jié)點,保證能遍歷到。
while(list1 != null && list2 != null){ //只要有一個鏈表到最后就停止循環(huán)
if(list1.val <= list2.val){ //較小的節(jié)點連到大節(jié)點上
next = list1.next;
list1.next = list2;
list1 = next;
} else{
next = list2.next;
list2.next = list1;
list2 = next;
}
}
return pNode1.val <= pNode2.val ? pNode1 : pNode2; //返回兩個頭節(jié)點中較小的那個.
}
}
方法2:遞歸方法
關(guān)鍵就是判斷l(xiāng)ist1和list2的val值的大小,然后改變list1或list2的next的指向.
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}else if(list2 == null){
return list1;
}
if(list1.val <= list2.val){
list1.next = Merge(list1.next,list2);
//這里是改變list1的next的指向,里面填list1.next是為了讓list1的節(jié)點向后移動一位.
return list1;
}else{
list2.next = Merge(list2.next,list1);
return list2;
}
}
}
遞歸方法參考牛客網(wǎng):披薩大叔的方法
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/75505.html
摘要：劍指中鏈表相關(guān)題目俗話說光說不練假把式，既然學(xué)習(xí)了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關(guān)題目。題目分析合并兩個排序的鏈表，需要分別比較兩個鏈表的每個值，然后改變指針。 溫故知新 鏈表由一個一個的作為節(jié)點的對象構(gòu)成的，每一個節(jié)點都有指向下一個節(jié)點的指針，最后一個節(jié)點的指針域指向空。每個節(jié)點可以存儲任何數(shù)據(jù)類型。 根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：拆分鏈表，將和進行拆分，保證原始鏈表不受影響。要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。輸入一個字符串長度不超過可能有字符重復(fù)字符只包括大小寫字母。遞歸，記錄一個當(dāng)前節(jié)點的位置，該位置指向最后一個節(jié)點時記錄一次排列。 1.復(fù)雜鏈表的復(fù)制 輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值，以及兩個指針，一個指向下一個節(jié)點，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的hea...
閱讀 2718·2021-11-25 09:43
閱讀 2099·2021-11-24 09:39
閱讀 1998·2021-11-17 09:33
閱讀 2770·2021-09-27 14:11
閱讀 1883·2019-08-30 15:54
閱讀 3239·2019-08-26 18:27
閱讀 1275·2019-08-23 18:00
閱讀 1825·2019-08-23 17:53
