方法一：递归

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
13         if(l1 == null)
14             return l2;
15         else if(l2 == null)
16             return l1;
17         else if(l1.val <= l2.val){
18             l1.next = mergeTwoLists(l1.next,l2);
19             return l1;
20         }else{
21             l2.next = mergeTwoLists(l1,l2.next);
22             return l2;
23         }
24     }
25 }

方法二：迭代法

 1 class Solution {
 2     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 3         //新建一个头结点用来存放结果
 4         ListNode head = new ListNode(0);
 5         ListNode res = head;
 6         while(l1 != null && l2 != null){
 7             if(l1.val <= l2.val){
 8                 res.next = l1;
 9                 l1 = l1.next;
10                 //System.out.println(res.val);
11             }else{
12                 res.next = l2;
13                 l2 = l2.next;
14             }
15             res = res.next;
16         }
17         res.next = l1 == null ?  l2 :  l1;
18         return head.next;
19     }
20 }