Leetcode 合并两个有序链表

地址：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/44/

题目

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

原解题思路

需要考虑的几种情况：

1. 两个链表均为空
2. 两个链表中的一个为空
3. 链表只有一个结点
4. 两个链表均有多个结点

如下代码中对前三种较特殊情况都作了相应的特殊处理。

代码（一）

/**
 * 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* root;   //返回值，合并后链表的头指针
        
        //1、2种情况
        if (l1 == NULL)   //考虑特殊情况，l1为空则合并后链表即为l2
            root = l2;
        else if (l2 == NULL)   //l2为空则合并后链表即为l1
            root = l1;
        //3、4种情况
        else    //都不为空则用常规方法合并
        {
            if (l1->val < l2->val)   //取根结点
            {
                root = l1;
                l1 = l1->next;
            }
            else
            {
                root = l2;
                l2 = l2->next;
            }
            ListNode* tail = root;   //合并链表的尾结点
            while (l1 != NULL || l2 !=NULL)   //可以直接写while(1)，循环内部根据l1或l2是否为空跳出循环
            {
                if (l1 == NULL)   //l1为空，把l2链在尾部即可
                {
                    tail->next = l2;
                    break;
                }
                else if (l2 == NULL)   //l2为空，把l1链在尾部即可
                {
                    tail->next = l1;
                    break;
                }
                if (l1->val < l2->val)
                {
                    tail->next = l1;   //将较小的l1链在尾部
                    tail = tail->next;   //tail后移
                    l1 = l1->next;   //l1后移
                }
                else   //同上
                {
                    tail->next = l2;
                    tail = tail->next;
                    l2 = l2->next;
                }
            }
        }
        return root;
    }
};

现解题思路

2020年5月1日更新

刚开始看到这个题目还是有印象做过的，但也没去找，就按着自己思路再做一遍。

其实写完后再找出之前做的看了看，思路几乎是一样的吧，大同小异。

特别需要注意的是， l1 和 l2 都是可能为空的，一般情况下都要将其做特殊处理。

这一次我一开始是想逐个比较 l1 和 l2 的结点大小然后构建一个新的链表的，写的过程中想到，似乎这么做有些麻烦，其实两个链表都是有序链表，任选一个链表来进行更新就可以了。但是选哪一个链表来进行更新是有讲究的，如果选的是第一个值较大的链表，那么就得把另一个链表的第一个结点插入到最前面，实际上这就很麻烦，所以我首先调整了两个链表 l1 和 l2 ，使 l1 始终是头结点较小的那个链表，然后将新构建的链表的头指针指向 l1 ，接下来就只需要逐个移动 l1 和 l2 进行比较和合并了，实际上就是把 l2 合并到 l1 中。

代码（二）

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