【每日一题025】leetcode-21

wuchangjian2021-11-04 07:35:57编程学习

目录

  • 题目
  • 思路
  • 相关思考
  • 代码1(C++/力扣)
  • 代码2(C++/力扣)

题目

题目来源
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路

1.数据结构“归并思路”,将二者合并
2.递归思路(太强了,这是怎么想到的…)

相关思考

1.在代码1的归并中,思考pi->next与newHead.next的区别,最后意识到pi指针是不停在变化的,指向的是最后处理的结点,而不是头节点(傻了傻了)
2.特别特别巧妙的一个思路,通过最后为空的判断条件终止递归,其他情况下挑出较小的那个值,然后对后面部分进行递归。

代码1(C++/力扣)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode newHead(0);
        ListNode *pi = &newHead;
        while(l1 && l2) {
            if(l1->val > l2->val) swap(l1, l2);
            pi->next = l1;
            l1 = l1->next;
            pi = pi->next;
        }
        pi->next = l1 ? l1 : l2;
        return newHead.next;
    }
};


代码2(C++/力扣)

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
    if(l1->val < l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}


相关文章

最新!长沙2022年秋季中小学收费标准出炉

最新!长沙2022年秋季中小学收费标准出炉

2022-08-26 20:10:10 暑假即将结束,长沙中小学生即将...

vue首屏优化方案

vue首屏优化方案

① 性能测试工具: Pingdom  Website Speed Test...

无症状≠无害,查出无症状脑梗死需要这样做

2022-08-18 17:32:49 长沙55岁的王阿姨今天拿到体检...

云计算---HCIA第一天

  计算机网络基础 HCIA --- 华为认...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。