题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
这到题目在leetcode和剑指 offer上均出现了，属于easy的题目，但是其中对链表的操作经常会让人搞错。
方法一：具体的思路就是设置一个result节点，令其依次根据list1与list2的较小值构建一个新的链表。
public class Solution {
public static ListNode Merge(ListNode list1,ListNode list2) {
ListNode res = new ListNode(0);
ListNode result = res; //重点！否则无法返回头节点
while(list1 != null || list2 != null) {
if(list1 == null) {
res.next = list2;
list2 = list2.next;
}else if(list2 == null) {
res.next = list1;
list1 = list1.next;
}else {
if(list1.val <= list2.val) {
res.next = list1;
list1 = list1.next;
}else {
res.next = list2;
list2 = list2.next;
}
}
res = res.next; //易错点
}
return result.next;
}
}
当程序输入空链表时，鲁棒性也得到了较好的保证。
除此之外，当对链表进行操作时，应注意
//这种方法可以用来遍历链表
list = list.next;
//这种方法相当于从链表中剔除了list.next，不可取
list.next = list.next.next;
方法二：还可以使用递归的思想来解决，leetcode上的高票答案大都也是使用递归。
public class Solution {
public static ListNode Merge(ListNode list1,ListNode list2) {
ListNode res = null;
if(list1 == null) return list2;
if(list2 == null) return list1;
if(list1.val <= list2.val) {
res = list1;
res.next = Merge(list1.next, list2);
}else {
res = list2;
res.next = Merge(list1, list2.next);
}
return res;
}
}
