题设
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
要点
- 链表归并
可以用递归来做。如果h1==null返回h2;如果h2==null返回h1；
否则，维护一个root，一个header=root,h1=l1,h2=l2。然后进行递归;
每次让header指向h1，h2中val较小的节点(如h1)，同时让header=header.next,h1=h1.next。
直到h1或h2为空。如果h1为空，则header=h2，否则相反，把剩下的节点都接上即可。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null)
return null;
if(l1 == null)
return l2;
if(l2 == null)
return l1;
ListNode root = new ListNode(0);
ListNode header = root;
ListNode h1 = l1;
ListNode h2 = l2;
merge(header , l1 , l2);
return root.next;
}
public void merge(ListNode header , ListNode h1, ListNode h2){
if(h1 == null){
header.next = h2;
return;
}
if(h2 == null){
header.next = h1;
return;
}
if(h1.val < h2.val){
header.next = h1;
header = header.next;
merge(header , h1.next , h2);
}
else{
header.next = h2;
header = header.next;
merge(header , h1 , h2.next);
}
}
