合并两个排序的链表

来源：牛客网 http://www.nowcoder.com/questionTerminal/d8b6b4358f774294a89de2a6ac4d9337

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。返回合并链表的头节点即可。

 1 class ListNode {
 2     int val;
 3     ListNode next = null;
 4 
 5     ListNode(int val) {
 6         this.val = val;
 7     }
 8 }
 9 public class TT {
10 
11     public static void main(String[] args) {
12         ListNode node1=new ListNode(1);
13         ListNode node2=new ListNode(2);
14         ListNode node3=new ListNode(3);
15         ListNode node4=new ListNode(4);
16         ListNode node5=new ListNode(5);
17         ListNode node6=new ListNode(6);
18 
19         node1.next=node3;
20         node3.next=node5;
21         node2.next=node4;
22         node4.next=node6;
23 
24         ListNode k = Merge(node1,node2);
25         while(k!=null){
26             System.out.print(k.val+" ");
27             k=k.next;
28         }
29 
30 
31     }
32 
33     public static ListNode Merge(ListNode list1,ListNode list2) {
34         if(list1==null) return list2;
35         else if(list2==null) return list1;
36         
37         ListNode p = new ListNode(0);
38         ListNode head=p; // 
39         while(true){
40             if(list1.val<=list2.val){
41                 p.next=list1;
42                 list1=list1.next;
43                 p=p.next;
44             }else{
45                 p.next=list2;
46                 list2=list2.next;
47                 p=p.next;
48             }
49 
50             if(list1==null){
51                 while(list2!=null){
52                     p.next=list2;
53                     p=p.next;
54                     list2=list2.next;
55                 }
56                 break;
57             }
58 
59             if(list2==null){
60                 while(list1!=null){
61                     p.next=list1;
62                     p=p.next;
63                     list1=list1.next;
64                 }
65                 break;
66             }
67         }
68 
69         return head.next;
70         
71     }
72 }

另一种递归写法：

 1 public ListNode Merge(ListNode list1, ListNode list2) {
 2     if (list1 == null)
 3         return list2;
 4     else if (list2 == null)
 5         return list1;
 6     ListNode mergeHead = null;
 7     if (list1.val < list2.val) {
 8         mergeHead = list1;
 9         mergeHead.next = Merge(list1.next, list2);
10     } else {
11         mergeHead = list2;
12         mergeHead.next = Merge(list1, list2.next);
13     }
14     return mergeHead;
15 
16 }