输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
方式一：（迭代）参考归并排序的Merge函数1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/*
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 root; //保留合并后的链表头
if(list1.val<=list2.val) root=list1;
else root=list2;
ListNode p1=list1;
ListNode p2=list2; //定义两个指针分别指向两个链表
ListNode head=new ListNode(-1); //创建一个结点来使后置结点指向下一个较小结点
//这里的val值无论是-1或其他值都无所谓
while((p1!=null)&&(p2!=null)){
if(p1.val<=p2.val){
head.next=p1; //让head(上个较小结点)的后置结点指向当前较小结点
head=p1; //更新head使其指向当前较小结点
p1=p1.next; //指针p1后移一位
}else{
head.next=p2;
head=p2;
p2=p2.next;
}
}
if(p1!=null) head.next=p1; //若list1有剩余
if(p2!=null) head.next=p2; //若list2有剩余
return root;
}
}
方式二：（递归）可由上面的迭代代码理解下列递归代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null) //参数非空判定；递归终止条件
return list2;
if(list2==null)
return list1;
ListNode phead; //定义一个指针用来指向当前较小结点
if(list1.val<=list2.val){
phead=list1;
phead.next=Merge(list1.next,list2);
}else{
phead=list2;
phead.next=Merge(list1,list2.next);
}
return phead;
}
}