链表相关知识总结:
1.表示空指针:推荐使用nullptr
,而不是NULL
2.注意题目所给链表的定义,随机应变
3.创建空节点
ListNode list=new ListNode() 初始化一个空节点,默认节点值为0(具体看题目中定义)
ListNode list=new ListNode(0) 初始化一个节点值为0的空节点,常用写法
4.区分 int* a
和 int *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 均按 非递减顺序 排列