链表合并

题解：

考察点： 链表，迭代，递归

易错点：

题目只给定链表，并不确定链表中元素的个数。很多同学不会读入。因为输入由整数和空格构成，建议当成字符串读入，使用按行读入，因为无法处理空格。同时推荐使用类对输入进行解析

很多同学不会写链表，其实链表的表示非常简单，可以定义为由值和指向下一个结点指针构成的结构体，同时C++ 中最好使用构造函数为和赋上初值

方法一：迭代

当链表和均不为空时，分别设置两个指针指向和，当中元素较小时，选取中的元素，并把的指针后移；当中元素较小时，选取中元素，并把指针后移。此时，如果还有剩余，将排序好的链表直接指向；如果还有剩余，则将排序好的链表指向

#include "bits/stdc++.h"
using namespace std;
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL){}
};
ListNode* merge(ListNode *l1,ListNode *l2){
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;
    ListNode *q=new ListNode(0);
    ListNode *p=q;
    while(l1&&l2){
        if(l1->val<l2->val){
            p->next=l1;
            l1=l1->next;
        }else{
            p->next=l2;
            l2=l2->next;
        }
        p=p->next;
    }
    if(l1){
        p->next=l1;
    }
    if(l2){
        p->next=l2;
    }
    return q->next;
}
int main()
{
    ListNode *l=new ListNode(0);
    ListNode *l1=l;
    int x,n=0;
    string s;
    getline(cin,s);
    stringstream ss1(s);
    while(ss1>>x){
        l1->next=new ListNode(x);
        l1=l1->next;
        ++n;
    }
    s="";
    getline(cin, s);
    stringstream ss2(s);
    ListNode *r=new ListNode(-1);
    ListNode *l2=r;
    while(ss2>>x){
        l2->next=new ListNode(x);
        l2=l2->next;
        ++n;
    }
    ListNode *res=merge(l->next,r->next);
    for(int i=0;i<n;i++){
        if(i==n-1){
            printf("%d\n",res->val);
        }else{
            printf("%d ",res->val);
        }
        res=res->next;
    }
    return 0;
}

方法二：递归

当和为空时，是递归的终止条件，因为此时只需要返回另一个链表即可。否则需要判断和哪一个头元素更小，然后递归地将更小那个视为下一个添加到结果里的值。

#include "bits/stdc++.h"
using namespace std;
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x),next(NULL){}
};
ListNode* merge(ListNode *l1,ListNode *l2){
    if(l1==NULL) return l2;
    if(l2==NULL) return l1;
    if(l1->val<l2->val){
        l1->next=merge(l1->next,l2);
        return l1;
    }else{
        l2->next=merge(l1,l2->next);
        return l2;
    }

}
int main()
{
    ListNode *l=new ListNode(0);
    ListNode *l1=l;
    int x,n=0;
    string s;
    getline(cin,s);
    stringstream ss1(s);
    while(ss1>>x){
        l1->next=new ListNode(x);
        l1=l1->next;
        ++n;
    }
    s="";
    getline(cin, s);
    stringstream ss2(s);
    ListNode *r=new ListNode(-1);
    ListNode *l2=r;
    while(ss2>>x){
        l2->next=new ListNode(x);
        l2=l2->next;
        ++n;
    }
    ListNode *res=merge(l->next,r->next);
    for(int i=0;i<n;i++){
        if(i==n-1){
            printf("%d\n",res->val);
        }else{
            printf("%d ",res->val);
        }
        res=res->next;
    }
    return 0;
}