题目描述

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

思路

设置一个“哨兵节点”叫 Head，这会让代码写起来非常“清爽”。整体流程如下：

• 如果 pHead1 和 pHead2，均没遍历完：

  • 如果 pHead1.val <= pHead2.val，那么当前 rt 的 next 指向 pHead1。并且移动 pHead1 指针。
  • 否则，当前 rt 的 next 指向 pHead2，移动 pHead2 指针。
  • 移动 rt 指针
  • 继续循环

• 否则，结束循环：

  • 如果 pHead1 未遍历完，rt 的 next 指向 pHead1
  • 如果 pHead2 未遍历玩，rt 的 next 指向 pHead2

时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。代码如下：

#include<bits/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){
        if(pHead1==NULL&&pHead2==NULL)return NULL;  //某个为空链表
        if(pHead1==NULL)return pHead2;
        if(pHead2==NULL)return pHead1;
        ListNode *p=pHead1,*q=pHead2,*head,*rt;
        if(pHead1->val<pHead2->val)head=pHead1,p=p->next;   //取链表首部最小的作为合并后链表首部
        else head=pHead2,q=q->next;
        rt=head;
        while(p!=NULL&&q!=NULL){    //合并两链表
            if(p->val<q->val)rt->next=p,p=p->next,rt=rt->next;
            else rt->next=q,q=q->next,rt=rt->next;
        }
        while(p!=NULL)rt->next=p,p=p->next,rt=rt->next; //将剩余的连接到新链表后面
        while(q!=NULL)rt->next=q,q=q->next,rt=rt->next;
        return head;
    }
};
int main(){
    Solution ac;
    ListNode head(1),head1(2);
    ListNode *root=&head;
    for(int i=3;i<=10;i+=2){
        root->next=new ListNode(i);
        root=root->next;
    }
    root=&head1;
    for(int i=4;i<=10;i+=2){
        root->next=new ListNode(i);
        root=root->next;
    }
    root=ac.Merge(&head,&head1);
    while(root!=NULL){
        cout<<root->val<<endl;
        root=root->next;
    }
    return 0;
}