剑指offer-合并两个排序的链表

- 日理万妓 2022-02-13 11:13 243阅读 0赞

#### 题目描述 ####

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

#### 算法思想 ####

合并两个有序的链表非常的简单。  
首先申请一个输出链表  
① 判断两个链表是否都为空，如果都为空返回空。  
② 判断两个链表谁小，将小的链表的节点放在输出链表上，然后再进行比较  
③ 当其中一个链表为空了，直接把剩下的不为空的链表接在输出链表后面即可

#### 代码实现 ####

#include <stdc++.h>
    
    using namespace std;
    
    
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };
    class Solution {
    public:
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        {
            ListNode* output = new ListNode(-1);
            ListNode* outputHead = output;
    
            if(pHead1 == NULL && pHead2 == NULL) return NULL;
            while(pHead1 != NULL && pHead2 != NULL)
            {
                if(pHead1->val <= pHead2->val)
                {
                    output->next = pHead1;
                    pHead1 = pHead1->next;
                    output = output->next;
                }
                else
                {
                    output->next = pHead2;
                    pHead2 = pHead2->next;
                    output = output->next;
                }
            }
            if(pHead1 == NULL && pHead2 != NULL)
                output->next = pHead2;
            if(pHead1 != NULL && pHead2 == NULL)
                output->next = pHead1;
            return outputHead->next;
    
        }
    };
    
    int main()
    {
        Solution S;
        //pHead1={1,3}
        //pHead2={2,4}
        ListNode* pHead1 = new ListNode(1);
        pHead1->next = new ListNode(3);
        ListNode* pHead2 = new ListNode(2);
        pHead2->next = new ListNode(4);
        ListNode* output = S.Merge(pHead1, pHead2);
        //输出合并之后的列表
        while(output != NULL)
        {
            cout << output->val << endl;
            output = output->next;
        }
        cout << "Hello world!" << endl;
        return 0;
    }

#### 运行截图 ####

codeblock运行上面代码截图：  
![在这里插入图片描述][2019042721302484.png]  
剑指offer截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]

#### 总结 ####

其实这个题非常的简单，但是有很多细节需要注意。  
第一个：申请output链表的时候一定给他一个初值，上面代码我给的初值是-1，如果不给初值，代码是通过不了的，个人认为应该是如果不给初值，代码并没有分配固定的指针，所以代码会出现错误。  
第二个：别忘了再申请一个outputHead指针指向输出链表，这样在以后的操作都可以用output->next，最后返回的时候可以返回outputHead->next，这种做法可以避免第一个数据需要单独处理的问题。  
第三个：上面代码中每一个需要合并的链表只有两个节点 ，第一个链表是1、3，第二个链表是2、4，如果增加节点，千万别忘传入合并函数的两个链表指针一定要指向链表的头结点。

[2019042721302484.png]: /images/20220213/b8c18a8892b24035abeea0a1e8ce74e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3doaWxlMTA_size_16_color_FFFFFF_t_70]: /images/20220213/e1f57d35236642808ca4975b961b9862.png