每日一题 剑指offer（合并两个排序列表）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

合并两个排序列表

题目描述

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

解析

·      比较两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前移动一个结点。

·      步骤一结果会有一个链表先遍历结束，或者没有

·      第三个链表尾结点指向剩余未遍历结束的链表

·      返回第三个链表首结点

代码

1class Solution {
2
3
4class Solution {
5public:
6    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
7    {
8        if (!pHead1 && !pHead2)return NULL;
9        if (!pHead1)return pHead2;
10        if (!pHead2)return pHead1;
11        ListNode *p = new ListNode(0);
12        ListNode *head = p;
13        while (pHead1 && pHead2)
14        {
15            if (pHead1->val < pHead2->val)
16            {
17                head->next = pHead1;
18                pHead1 = pHead1->next;
19            }
20            else
21            {
22                head->next = pHead2;
23                pHead2 = pHead2->next;
24            }
25            head = head->next;
26        }
27        if (pHead1)
28            head->next = pHead1;
29        if (pHead2)
30            head->next = pHead2;
31        return p->next;
32    }
33};