2021-04-24 LeetCode 21. 合并两个有序链表

链表相关知识总结:

1.表示空指针:推荐使用nullptr,而不是NULL
2.注意题目所给链表的定义,随机应变
3.创建空节点

ListNode list=new ListNode() 初始化一个空节点,默认节点值为0(具体看题目中定义)
ListNode list=new ListNode(0) 初始化一个节点值为0的空节点,常用写法

4.区分 int* aint *a
http://www.cppblog.com/tiger7/articles/146072.html
5.使用-> 获取val值 p->val;指向next q->next
6.if()中应该比较的大小,即l1、l2中val值的大小,而不是比较l1、l2两个链表本身

7.!!!(踩坑处,怪我太菜了╮(╯▽╰)╭)
定义的 l3、r的next值都是nullptr,所以合并节点时 l1 应该指向r->next,而不是指向r。否则会造成从始至终根本没有节点合并到 l3 链表上,最后代码返回结果为空

  • 错误写法过程分析:
    进入while第①次循环:
    r = l1;//l1指向r本身
    r = r->next; //观察题目给的ListNode定义,定义的 l3、r的next值都是nullptr,所以此时r相当于被赋值nullptr

  • 进入while第②次循环:
    r = l1; //由于第一次循环最后r被赋值nullptr,所以此时 l1 指向了nullpte,根本没有合并到 r 上(即 l3 链表上)

  • 所以之后的循环全部无效o(╥﹏╥)o

8.最后返回的是l3->next,因为l3本身是头指针,val值默认为0,从l3->next开始才是合并链表的第一个节点,对应的val值才是合并链表中的第一个值(即最小值)

  • 错误代码分析:
    return l3;//最后结果最前面多了一个头指针默认值0
    测试用例下错误结果[0,1,1,2,3,4,4],实际正确结果[1,1,2,3,4,4]

代码如下:

迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {} //没有参数值,默认val为0,next为nullptr
 *     ListNode(int x) : val(x), next(nullptr) {} //有1个参数x,默认val为x,next为nullptr
 *     ListNode(int x, ListNode *next) : val(x), next(next) {} //有2个参数x、*next,默认val为x,next为next
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        /**
         * 定义指针
         */
        ListNode* l3 = new ListNode(0);//定义一个指向空节点的指针,作为哨兵节点 (根据题目提供的ListNode定义,可以是ListNode() or ListNode(0) or ListNode(-1))
        ListNode* r = l3;//定义另一个指针r,和l3指向同一地方

        /**
         * 找较小节点合并
         */
        //如果l1,l2链表均不为空,则执行while循环
        while(l1 && l2){
            //如果l1的val小于l2的,则哨兵指针的next指向l1(即小的那个)
            if(l1->val <= l2->val){
               r->next = l1;
               l1 = l1->next;//l1指针向后移一个
            }else{
               r->next = l2;//反之同理,指向l2的(即小的那个)
               l2 = l2->next;//l2指针向后移一个
            }
           r = r->next;//在if else中r->next已更新,这里将r向后移一个,若满足条件继续循环
        }

        /**
         * 合并剩余节点
         */        
        r->next = l1 != nullptr ? l1:l2;//问号表达式:判断l1,l2哪一个不为空,则r->next就指向哪个,直接将剩余的所有节点拼接到l3中
        return l3->next;
    }
};

题目:

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

示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:
输入:l1 = [], l2 = []
输出:[]

示例 3:
输入:l1 = [], l2 = [0]
输出:[0]

提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

上一篇:重排链表——leetcode26


下一篇:刷题-力扣-面试题 02.05. 链表求和