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