问题描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = [] 输出:[]
示例 3:
输入:l1 = [], l2 = [0] 输出:[0]
思路:
类比数组的合并,比较两个链表之前元素的大小,将其归纳到另一个链表。
目录
问题描述:
解决代码:
代码解析:
1.
2.
3.
4.
需要注意的是,当完成遍历之后,此时cur2有可能时NULL!
5.
需要注意的是
6.
ps:
解决代码:
以list2为主体,将list1合并到list2
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* prev = NULL; //不可以放在循环内部,否则会出现空指针问题while(cur1 && cur2){if(cur1->val <= cur2->val){if(cur2 == list2){list1 = cur1->next;cur1->next = cur2;cur2 = cur1;cur1 = list1;list2 = cur2;}else{list1 = cur1->next;cur1->next = cur2;prev->next = cur1;prev = cur1;cur1 = list1;}}else{prev = cur2;cur2 = cur2->next;}}//此时cur2已经是NULL,不能以用cur2//prev本身初始化时就是NULL!所以需要判断! cur1若全部添加到cur2之后,那么cur1也是NULL,所以cur1也需要断言。//判断要写在解引用语句之前!如果已经去解引用了,那么判断将无意义!if(cur1 && prev && prev->val < cur1->val) //如果list2遍历结束,都找出不大于cur1->val的值prev->next = cur1;if(list2) //注意是否为空!return list2;elsereturn list1;
}
代码解析:
1.
struct ListNode* cur1 = list1;
struct ListNode* cur2 = list2;
struct ListNode* prev = NULL; //不可以放在循环内部,否则会出现空指针问题
既然要遍历整个链表,那就要建立cur指针,不断往下移动,从而完成遍历。
对于链表的链接,需要一个prev指针,将链表的上一个节点与下一个节点链接。
2.
if(cur1->val <= cur2->val){
if(cur2 == list2){
list1 = cur1->next;
cur1->next = cur2;
cur2 = cur1;
cur1 = list1;
list2 = cur2;
}
在小于等于的前提下,当cur2从list2开始的时候,此时需要给list2“换头”。即需要把head1的元素整合到list2头部,所以要 list2 = cur2;
3.
else{
list1 = cur1->next;
cur1->next = cur2;
prev->next = cur1;
prev = cur1;
cur1 = list1;
}
当完成换头之后,此时只需要将list1中的节点连接到list2中。
4.
else{
prev = cur2;
cur2 = cur2->next;
}
这段代码表示,当无法满足 if(cur1->val <= cur2->val)时,需要让cur2往下遍历,找到满足if语句的节点。
需要注意的是,当完成遍历之后,此时cur2有可能时NULL!
5.
if(cur1 && prev && prev->val < cur1->val) //如果list2遍历结束,都找出不大于cur1->val的值
prev->next = cur1;
我们的思路是让cur2不断往下遍历,但是若最后的节点的val仍然小于cur1的val,此时cur1并没有完成遍历,只需要让cur1剩下的元素,连接到cur2尾部即可。
需要注意的是
cur1 && prev 该判断语句必须要添加,并且需要写在if语句的前半部分!
//判断要写在解引用语句之前! 如果已经去解引用了,那么判断将无意义!
原因:①prev初始化时为NULL,所以要让prev进行判断
②需要判断cur1有没有走到最后的NULL指针。
③需要用prev->val 而不是 cur2->val,此时cur2已经跳出while循环,说明cur2已经是空指针!
6.
if(list2) //注意是否为空!
return list2;
else
return list1;
}
最后,当list2本身为空的,则需要返回list1
ps:
通过刷leetcode可知,leetcode的题目往往会给出很抽象的数据范围,链表本身就可能是空链表!!!