2023-9-7
9-7
链表
题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路 这是一道很经典的链表题，最后学到了两个思路，递归和双指针。
在这里总结一下递归：递归就像是把事情分包给了另外一个人完成，一轮中只关注自己的事情，且一定有终止条件，否则会永远递归下去
关于return L1的个人理解: 递归的核心在于,我只关注我这一层要干什么,返回什么,至于我的下一层(规模减1),我不管,我就是甩手掌柜.
好,现在我要merge L1,L2.我要怎么做?
- 显然,如果L1空或L2空,我直接返回L1或L2就行,这很好理解.
- 如果L1第一个元素小于L2的? 那我得把L1的这个元素放到最前面,至于后面的那串长啥样 ,我不管. 我只要接过下级员工干完活后给我的包裹, 然后把我干的活附上去(令L1->next = 这个包裹)就行
- 这个包裹是下级员工干的活,即merge(L1->next, L2)
我该返回啥?
- 现在不管我的下一层干了什么,又返回了什么给我, 我只要知道,假设我的工具人们都完成了任务, 那我的任务也就完成了,可以返回最终结果了
- 最终结果就是我一开始接手的L1头结点+下级员工给我的大包裹,要一并交上去, 这样我的boss才能根据我给它的L1头节点往下找,检查我完成的工作
思路一 递归
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if(list1===null){
return list2
}
else if(list2===null){
return list1
}
else if(list1.val<list2.val){
list1.next = mergeTwoLists(list1.next,list2)
return list1
}else{
list2.next = mergeTwoLists(list1,list2.next)
return list2
}
};
思路二 双指针
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let dum = new ListNode(0),cur = dum
while(list1 !==null&&list2!==null){
if(list1.val<list2.val){
cur.next =list1
list1 = list1.next
cur = cur.next
}
else if(list1.val>=list2.val){
cur.next = list2
list2 = list2.next
cur = cur.next
}
}
cur.next = list1 !==null ? list1 :list2
return dum.next
};