给定两个递增的链表，合并成一个递增链表
如给1 3 5和2 4 6，合并后该为1 2 3 4 5 6
非递归方法
public ListNode merge(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list2 == null && list1 == null) {
return null;
}
ListNode newStart, temp, temp2;
newStart = list1;
while (list1 != null && list2 != null) {
temp = null;
temp2 = null;
if (list1.val <= list2.val) {
while (list1 != null && list1.val <= list2.val) {
// 如果list2结点的值大于list1，将list1引用向后移
// 直至list1的值大于list2或者list1为null
// temp保存list1前面的结点，方便后面的插入操作
temp = list1;
list1 = list1.next;
}
}
// temp2指向list2后面的结点
temp2 = list2.next;
// 这种情况表示list1指向第一个结点，也就是list1的第一个结点值小于list2第一个节点值
if (temp == null) {
list2.next = list1;
// newStart为新的链表头结点
newStart = list2;
} else {
// list2插入到list1中间
list2.next = temp.next;
temp.next = list2;
}
// 移动list2指向下一个结点
list2 = temp2;
}
return newStart;
}
递归方法
public ListNode merge(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 如果list1的值小于list2，将list1后面的结点和list2进行合并
if (list1.val <= list2.val) {
list1.next = merge(list1.next, list2);
return list1;
} else {
// 否则将list2后面的结点跟list1进行合并
list2.next = merge(list1, list2.next);
return list2;
}
}
