1.题目描述

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

2.算法设计思路

1）总体思路：

以原链表中的值，新建一个链表，并保持有序。

如果直接将原链表中的结点接过来，问题会变得麻烦很多。我以前做过一次直接转移结点的，可参考：合并两个有序单链表，对象析构这一着我实在没想到

2）算法过程：

新建一个头指针 p，指向空。
使用两个指针 p1 和 p2 分别指向两个链表的头部，然后同时遍历两个链表。
每次遍历，创建一个新的结点连接到新链表尾部，然后比较 p1 和 p2 指向的结点中元素的值，并将较小的一个值存放到新结点中，同时相应的指针（p1 或 p2）向后移动一步。
停止遍历条件：p1 为空或 p2 为空。
将原链表中剩余元素的值转移到新链表中（如果有的话）。

3）遇到问题：

第一个结点的处理： 在创建新结点时，新链表可以处于两种状态：为空或不为空，因此需要分别考虑。

    if(p == nullptr){
                p = t;
                pHead = p;
            }else{
                p->next = t;
                p = p->next;
            }

原链表为空： 如果初始恰有一个原链表为空（另一个不为空），就会直接到第5步，转移原链表中的剩余元素，而此时新链表的头结点尚为空，操作p->next 就会出现问题。

//初始代码
    while(p3 != nullptr){
            p->next = new ListNode(0);
            p = p->next;
            p->val = p3->val;
            p3 = p3->next;
        }

可以仿照问题 1 的方式，加一个分支判断。

//修改方案一
//p3:指向第一个剩余的元素
    while(p3 != nullptr){
            if(p == nullptr){
                p = new ListNode(0);
                pHead = p;
            }else{
                p->next = new ListNode(0);
                p = p->next;
            }
            p->val = p3->val;
            p3 = p3->next;
        }

但这样的代码看起来比较难看。我们也可以在函数头部打个下面这样的“补丁”。

//修改方案二
    if(pHead1 == nullptr){
            return pHead2;
        }else if(pHead2 == nullptr){
            return pHead1;
        }

4）尝试优化代码

代码优化我目前觉得主要有两个方面：运行效率与可读性。我比较希望代码可以集中地的展现思路、更加简练。

例如，关于遍历过程移动链表指针的操作，对比一下下面两段代码：

//代码段一
            if(x1 < x2){
                p1 = p1->next;
            }else{
                p2 = p2->next;
            }

//代码段二
            ListNode** p3 = x1 < x2 ? &p1 : &p2;
            *p3 = (*p3)->next;

我会比较喜欢第二段代码，因为它移动指针的操作就集中在一步：*p3 = (*p3)->next; 。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

最终代码，C++实现：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == nullptr){
            return pHead2;
        }else if(pHead2 == nullptr){
            return pHead1;
        }

        ListNode* pHead = nullptr;
        ListNode* p = nullptr;
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;

        while(p1 != nullptr && p2 != nullptr){
            ListNode* t = new ListNode(0);
            int x1 = p1->val;
            int x2 = p2->val;

            t->val = x1 < x2 ? x1 : x2;
            if(p == nullptr){
                p = t;
                pHead = p;
            }else{
                p->next = t;
                p = p->next;
            }

            ListNode** p3 = x1 < x2 ? &p1 : &p2;
            *p3 = (*p3)->next;
        }

        ListNode* p3 = nullptr;
        p3 = p1 != nullptr ? p1 : p2;

        while(p3 != nullptr){
            p->next = new ListNode(0);
            p = p->next;
            p->val = p3->val;
            p3 = p3->next;
        }
        return pHead;
    }
};