問(wèn)題描述
????輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則蒙幻。
解題思路
????利用遞歸的思想嘱腥，比較當(dāng)前節(jié)點(diǎn)值的大小，然后使用遞歸朽色。合并過(guò)程中邻吞，每次都是從兩個(gè)鏈表中找出較小的一個(gè)來(lái)連接，因此可以采用遞歸來(lái)實(shí)現(xiàn)：當(dāng)任意一個(gè)鏈表為null時(shí)葫男，直接連接接另一個(gè)鏈表即可抱冷；其余情況只需要在兩個(gè)鏈表中找出較小的一個(gè)結(jié)點(diǎn)進(jìn)行連接接，該結(jié)點(diǎn)的next值繼續(xù)通過(guò)遞歸函數(shù)來(lái)連接
/**
* 鏈表合并
*/
public class MergeList {
private static class ListNode{
int val;
ListNode next=null;
public ListNode(int val) {
this.val = val;
}
}
/**
*
* @param list1
* @param list2
* @return
* 將兩個(gè)鏈表的合并
*/
public static ListNode Merge(ListNode list1,ListNode list2) {
//魯棒性考慮
if (list1==null){
return list2;
}else if (list2==null){
return list1;
}
ListNode head=null;
//常規(guī)解法
if (list1.val<list2.val){
head=list1;
head.next=Merge(list1.next,list2);
}else {
head=list2;
head.next=Merge(list1,list2.next);
}
return head;
}
public static void main(String[] args) {
ListNode list1=new ListNode(1);
list1.next=new ListNode(3);
list1.next.next=new ListNode(5);
ListNode list2=new ListNode(2);
list1.next=new ListNode(4);
list1.next.next=new ListNode(6);
ListNode listNode=Merge(list1,list2);
while (listNode!=null){
System.out.print(listNode.val);
listNode=listNode.next;
}
}
}
