給定兩個遞增的鏈表笋敞，合并成一個遞增鏈表
如給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結(jié)點(diǎn)的值大于list1松捉，將list1引用向后移
// 直至list1的值大于list2或者list1為null
// temp保存list1前面的結(jié)點(diǎn)栅屏，方便后面的插入操作
temp = list1;
list1 = list1.next;
}
}
// temp2指向list2后面的結(jié)點(diǎn)
temp2 = list2.next;
// 這種情況表示list1指向第一個結(jié)點(diǎn)，也就是list1的第一個結(jié)點(diǎn)值小于list2第一個節(jié)點(diǎn)值
if (temp == null) {
list2.next = list1;
// newStart為新的鏈表頭結(jié)點(diǎn)
newStart = list2;
} else {
// list2插入到list1中間
list2.next = temp.next;
temp.next = list2;
}
// 移動list2指向下一個結(jié)點(diǎn)
list2 = temp2;
}
return newStart;
}
遞歸方法
public ListNode merge(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 如果list1的值小于list2耸彪，將list1后面的結(jié)點(diǎn)和list2進(jìn)行合并
if (list1.val <= list2.val) {
list1.next = merge(list1.next, list2);
return list1;
} else {
// 否則將list2后面的結(jié)點(diǎn)跟list1進(jìn)行合并
list2.next = merge(list1, list2.next);
return list2;
}
}
