21.合并两个排序的列表（Merge Two Sorted Lists）

题目：合并两个排序的链接列表，并将其作为新列表返回。新列表应通过拼接前两个列表的节点进行。

方法一：

思路:（1）首先使l1指向首节点值较小的链表；

（2）将链表l2的首节点，连接在链表l1中节点的值小于l2首节点的值最后一个结点之后；

（3）将链表l1中大于l2首节点值的第一个节点，连接在l2中小于，链表l1大于链表l2首节点的第一个节点，的最后一个节点之后；

（4）更改l2首节点;

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11         
12         if(l1==null){//若l1为空则直接返回l2
13             
14             return l2;
15             
16         }
17         
18         if(l2==null){//若l2为空则直接返回l1
19             
20             return l1;
21             
22         }
23         
24         ListNode temp1=l1;
25         
26         if(l1.val>l2.val){//使l1指向首节点值较小的链表
27             
28             l1=l2;
29             l2=temp1;
30             
31         }
32         
33         temp1=l1;
34         while(temp1!=null&&l2!=null){
35             
36             ListNode temp2=l2;
37             
38             //找到第一个比temp2.val大的节点
39             while(temp1.next!=null&&temp1.next.val<temp2.val){
40                 
41                 temp1=temp1.next;
42                 
43             }
44             
45             //若l1所有节点的值都小于temp2.val，则将l2接在temp1节点之后
46             if(temp1.next==null){
47                 
48                 temp1.next=l2;
49                 return l1;
50                 
51             }
52             
53             //若l1中存在比temp2.val值大，则在l2中找到小于temp1.next.val的最后一个节点
54             while(temp2.next!=null&&temp1.next.val>temp2.next.val){
55                 
56                 temp2=temp2.next;
57                 
58             }
59             
60             //若l2所有节点的值都小于temp1.next.val则将l2插在l1的temp1节点之后
61             if(temp2.next==null){
62                 
63                 temp2.next=temp1.next;
64                 temp1.next=l2;
65                 
66                 return l1;
67                 
68             }
69             
70             //若l2中存在比temp.next.val值大的节点，则将l2从头结点到temp2节点插在l1的temp1节点之后;并且将temp2.next作为l2的头节点；
71             ListNode temp=l2;
72             l2=temp2.next;//将temp2.next作为l2的头节点
73             
74             temp2.next=temp1.next;
75             temp1.next=temp;
76             
77         }
78         
79         
80         return l1;
81     }
82 }

方法二：利用递归

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 class Solution {
10     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11         
12         if(l1==null){
13 
14             return l2;
15             
16         }
17         if(l2==null){
18             
19             return l1;
20             
21         }
22         
23         ListNode mergehead;
24         if(l1.val<l2.val){
25             
26             mergehead=l1;
27             mergehead.next=mergeTwoLists(l1.next,l2);
28             
29         }else{
30             
31             mergehead=l2;
32             mergehead.next=mergeTwoLists(l1,l2.next);
33             
34         }
35         
36         return mergehead;
37     }
38 }