题目描述
两个升序链表合并为一个新的升序链表。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解析
考察重点：迭代实现与递归实现
实现方法
- 方法一：迭代实现很简单，两个指针分别遍历两个链表，比较当前结点的大小，依次链接到新表上即可。
- 方法二：递归实现，递归是算法设计中常用的技巧，函数调用自己本身，局部求解最后得出全部求解。比较两个链表的第一个结点，从链表中取下较小的元素的结点，余下部分形成新的链表与另外一个链表再做合并，依次递归。
实现技巧：
递归实现在算法设计中得到广泛的应用。
迭代实现代码
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*如果其中一个链表为null，则返回另一个链表即可*/
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode head = new ListNode(-1);//定义结果的头结点
ListNode tail = head;//定义结果的尾指针
while(l1 != null && l2 != null){//遍历两个链表按照数据升序链接到新的链表中
if(l1.val < l2.val){
tail.next = l1;
tail = tail.next;
l1 = l1.next;
}else {
tail.next = l2;
tail = tail.next;
l2 = l2.next;
}
}
/*其中一个链表先遍历完全，另外一个链表链接到新表尾部即可*/
if(l1 == null){
tail.next = l2;
}else{
tail.next = l1;
}
ListNode res = head.next;//指向新表的第一个结点
head.next = null;//帮助GC回收head结点
return res;
}
递归实现代码
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
/*递归结束的条件，如果有一个链表为null，则返回另一个链表，不再执行递归操作*/
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
/*定义res指向两个链表中元素较小的结点*/
ListNode res;
/*取出元素较小结点，余下部分组成新的链表*/
if(l1.val < l2.val){
res = l1;
l1 = l1.next;//余下部分组成新的链表l1
}else {
res = l2;
l2 = l2.next;//余下部分组成新的链表l2
}
res.next = mergeTwoLists(l1, l2);//递归调用，res的next指向新的两个链表合并结果
return res;
}
总结
迭代实现易于理解、编码复杂，递归实现编码简单，但对于初学者难理解。不过两种方法都是算法设计中的重点，更好的掌握和理解对于解决问题很有用。未来还会遇到其他的需要两种方法实现的算法，例如最经典的就是树的遍历，递归实现和迭代实现（非递归实现）。
