来源：牛客网 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 }