问题描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路
利用递归的思想，比较当前节点值的大小，然后使用递归。合并过程中，每次都是从两个链表中找出较小的一个来连接，因此可以采用递归来实现：当任意一个链表为null时，直接连接接另一个链表即可；其余情况只需要在两个链表中找出较小的一个结点进行连接接，该结点的next值继续通过递归函数来连接
/**
* 链表合并
*/
public class MergeList {
private static class ListNode{
int val;
ListNode next=null;
public ListNode(int val) {
this.val = val;
}
}
/**
*
* @param list1
* @param list2
* @return
* 将两个链表的合并
*/
public static ListNode Merge(ListNode list1,ListNode list2) {
//鲁棒性考虑
if (list1==null){
return list2;
}else if (list2==null){
return list1;
}
ListNode head=null;
//常规解法
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;
}
}
}
