題目描述
輸入兩個單調(diào)遞增的鏈表瞻鹏，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則鹿寨。
代碼實(shí)現(xià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) return list2;
if(list2 == null) return list1;
ListNode head = null;
if(list1.val <= list2.val){
head = list1;
list1.next = Merge(list1.next,list2);
}
else{
head = list2;
list2.next = Merge(list1,list2.next);
}
return head;
}
}
主要思路
1新博、首先處理空鏈表，當(dāng)其中一個為空鏈表時脚草，直接輸出另一個赫悄；當(dāng)兩個均為空鏈表時，輸出null
2馏慨、比較 list1 和 list2 的頭結(jié)點(diǎn)埂淮，較小的頭結(jié)點(diǎn)作為合并后新鏈表的頭結(jié)點(diǎn)
3、確定新鏈表的頭結(jié)點(diǎn)之后写隶，就可以遞歸比較余下的結(jié)點(diǎn)了
附：非遞歸實(shí)現(xià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) return list2;
if(list2 == null) return list1;
//創(chuàng)建一個 val 為0的結(jié)點(diǎn)
ListNode head = new ListNode(0);
ListNode root = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
head.next = list1;
list1 = list1.next;
} else {
head.next = list2;
list2 = list2.next;
}
head = head.next;
}
if (list1 != null) {
head.next = list1;
}
if (list2 != null) {
head.next = list2;
}
return root.next;
}
}
