题解 | #合并两个排序的链表#

C语言思路：

第一步，首先看两个表其中是否有一个表是空表，是则返回另一个链表(不需要合并操作)；

第二步，若都不为空，就初始化一个头结点作为合并后的表头结点，然后依次比较两个链表中的结点值，值小的就插入新表中，然后指针后移继续比较，重复此操作直至其中一个表为空或者都为空；

第三步，当两个表表长不一致时，即其中一个表的元素已经全部被插入到新表中了，由于两个表都是有序表，那么另外一个表中剩下的节点元素值自然都比已经新表中的节点元素值大，于是就直接把剩下的节点直接拼接到合并的新表后面即可。

运行时间：4ms 占用内存：512KB

代码(C)实现如下：

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {

    // write code here

    if(pHead1==NULL){

        return pHead2;

    }

    if(pHead2==NULL){

        return pHead1;

    }

    struct ListNode* Head;

    Head = (struct ListNode *)malloc(sizeof(struct ListNode));

    struct ListNode* p = Head;

    while(pHead1!=NULL&&pHead2!=NULL)

    {

        if(pHead1->val > pHead2->val)

        {

            p->next = pHead2;

            pHead2 = pHead2->next;

            p = p->next;

        }else{

            p->next = pHead1;

            pHead1 = pHead1->next;

            p = p->next;

        }

    }

    if(pHead1==NULL){

        p->next = pHead2;

    }

    if(pHead2==NULL){

        p->next = pHead1;

    }

    return Head->next;

}