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

题目难度：简单
考察内容：链表
题目简介：给两个非递减单链表l1, l2，合并为一个非递减的单链表。

1.问题分析
给了两个非递减的单链表，合并成一个非递减的单链表，这个问题和归并排序的思想很像
回忆下归并排序，(l,mid)和(mid+1,r)排好序后合并，下面给出代码

void m_sort(int q[],int l,int r)
{
    if(l>=r)return ;
    int mid=l+r>>1;
    m_sort(q,l,mid),m_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])tem[k++]=q[i++];
        else tem[k++]=q[j++];
    }
    while(i<=mid)tem[k++]=q[i++];
    while(j<=r)tem[k++]=q[j++];
    for(int i=l,j=0;i<=r;i++,j++)q[i]=tem[j];
}

具体方法为利用单调性每次加入一个元素，最后剩下的全部加入，所以复杂度是O(n+m)的
这题是将链表合并，思想还是一样的，每次连接较小的一个数，最后剩下的全部连接
具体过程如下图

这里设置了一个虚拟头节点，也叫哨兵节点，避免空指针异常

 ListNode *vhead = new ListNode(-1);
        ListNode *cur = vhead;

下面就很好实现代码了

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode *vhead = new ListNode(-1);
        //设置虚拟头节点
        ListNode *cur = vhead;
        while (pHead1 && pHead2) {//两个链表任意一个为空都会跳出循环，因为此时只需将剩下的全部链接即可
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            //指向较小的一个数
            else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
    }
};