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
原文链接:【http://xie.infoq.cn/article/d471398492df328cf7690fb12】。文章转载请联系作者。
猫吃小怪兽

 关注
还未添加个人签名 2019.12.17 加入
还未添加个人简介
发布
暂无评论