题目:合并两个排序的链表
描述:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
思路:
非递归:同时遍历两个链表,每次都比较下它们俩结点值,哪个链表结点用过了就让他往后走一步
递归:比较list1和list2,谁小就递归调用该链表的.next继续执行
递归的感觉就是在栈里,把list1和list2的结点全部拆赋值给局部变量p,按序排好了
最后递归结束,p被从栈里依次弹出
比如: 递归执行到最后一步时,这时候栈里充满了p
栈顶
7
4
3 递归结束=> 栈顶依次弹出 p=7 p=4->7 p=3->4->7 p = 3->3->4->7 p=2->3->3->4->7
3
2
栈底
//递归版
public ListNode Merge1(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode p = null;
if (list1.val < list2.val) {
p = list1;
p.next = Merge1(list1.next, list2);
} else {
p = list2;
p.next = Merge1(list1, list2.next);
}
return p;
}
//非递归
public ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode p = null;
//这一步是为了给p搞个头结点,因为下面的while里直接用的next来拼接
if (list1.val < list2.val) {
p = list1;
list1 = list1.next;
} else {
p = list2;
list2 = list2.next;
}
ListNode result = p;
while (list1 != null || list2 != null) {
if (list1 != null && list2 != null) {
//谁小拼谁
if (list1.val < list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
}
//list1为null就只管把list2拼上就行
else if (list1 == null) {
p.next = list2;
list2 = list2.next;
}
//只管拼list1
else {
p.next = list1;
list1 = list1.next;
}
p = p.next;
}
return result;
}