Algorithm week 1: Merge Two Sorted Lists

用户头像
猫吃小怪兽
关注
发布于: 2020 年 05 月 24 日

基础题,合并两个有序链表。



思路很简单,用两个指针分别指向两条链表当前的未合并结点,总是取较小值加入结果串。

过程中需要注意边界情况处理:链表为空,链表只包含一个结点,链表遍历到尾部,返回指针应该指向结果串的头部。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head1 = NULL, *head2 = NULL, *ret = NULL;
if (l1 == NULL) return l2;
else if (l2 == NULL) return l1;
else if (l1->val > l2->val) {
ret = l2;
head2 = l2->next;
head1 = l1;
} else {
ret = l1;
head1 = l1->next;
head2 = l2;
}
ListNode* tmp = ret;
while (1) {
if (head1 == NULL) {
tmp->next = head2;
break;
} else if (head2 == NULL) {
tmp->next = head1;
break;
} else if (head1->val > head2->val) {
tmp->next = head2;
head2 = head2->next;
} else {
tmp->next = head1;
head1 = head1->next;
}
tmp = tmp->next;
}
return ret;
}
};



但是其实前面给结果串赋头结点的情况处理得有点复杂了,如果利用哨兵(给ret单独的头结点)可以再简化一下编程。链表遍历完的情况也可以统一挪出来单独处理,l1和l2也不需要保留原样(对于做题来说)。

简化完会有一个赏心悦目的版本:

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* ret = new ListNode(-1);
ListNode* tmp = ret;
while(l1 && l2){
if (l1->val > l2->val) {
tmp = l2;
l2 = l2->next;
} else {
tmp = l1;
l1 = l1->next;
}
tmp = tmp->next;
}
// 若有遍历完的链表,加到尾部
tmp->next = l1 == NULL ? l2 : l1;
return ret->next;
}
};



当然还存在最简洁的递归写法,代价是由于需要m+n次压栈,空间复杂度由O(1)升为O(M+N)。对于小规模数据来说完全没有问题。

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1)
return l2;
if(!l2)
return l1;
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
};



写链表的时候需要额外留意边界条件处理

  • 如果链表为空时,代码是否能正常工作?

  • 如果链表只包含一个结点时,代码是否能正常工作?

  • 如果链表只包含两个结点时,代码是否能正常工作?

  • 代码逻辑在处理头结点和尾结点的时候,是否能正常工作?



哨兵结点的加入(单独的头、尾结点,拒绝插入空链表/删一个结点的链表等special case)也可以有效简化编程。



发布于: 2020 年 05 月 24 日 阅读数: 43
用户头像

猫吃小怪兽

关注

还未添加个人签名 2019.12.17 加入

还未添加个人简介

评论

发布
暂无评论
Algorithm week 1: Merge Two Sorted Lists