链表合并

其实这个题就是合并两个有序链表，如果按照作弊的方法呢，就可以不把这个东西当作链表，直接把这个东西当作数组，即直接把两个有序数组进行排序，就跟之前说过的归并排序差不多，类似代码如下：

int a[15],b[15],c[15];
void Merge_Sort(int n, int m)///n是数组a的长度，m是数组b的长度
{
    int i, j, k;
    i = j = k = 0;
    while(i<n && j<m)
    {
        if(a[i] < b[j])///因为是已经排好序的只要a[i]比b[j]小i就后移
            c[k++] = a[i++];
        else///同理
            c[k++] = b[j++];
    }
    while(i < n)///这个是b数组已经全部比完
        c[k++] = a[i++];
    while(j < m)///这个是a数组已经全部比完
        c[k++] = b[j++];
}

那么如果这个题目采用链表的方式的话，其实跟上述的方法差不多，也是一个个比较，但是有所不同的是通过链表的方式进行比较，首先就是写一个创建一个新链表的函数，然后在写一个合并链表的函数。创建链表就可以用我们处理过输入之后的vector当作链表的输入，然后创建一个头节点，即 ListNode *head = new ListNode;然后在创建一个当前节点now=head用来遍历，在创建一个临时节点用来当作now->next，最后返回head就可以了，链表的合并时最基础的东西，这个具体的实现方式还是直接看代码把。

算法实现：

#include <bits/stdc++.h>
using namespace std;
struct ListNode{
    int val;
    ListNode *next;
};
ListNode* creatList(string s){
    stringstream ss(s);
    vector<int> a;
    int x;
    while(ss >> x) a.push_back(x);
    ListNode *head = new ListNode;
    head->val = a[0];
    ListNode* now = head;
    for(int i=1; i<a.size(); i++){
        ListNode *tmp = new ListNode;
        tmp->val = a[i];
        tmp->next = nullptr;
        now->next = tmp;
        now = now->next;
    }
    return head;
}
ListNode* mergeList(ListNode* h1, ListNode* h2){
    if(h1 == nullptr) return h2;
    if(h2 == nullptr) return h1;
    ListNode *head = new ListNode;
    ListNode *now = head;
    while(h1 && h2) {
        int x;
        if(h1->val < h2->val) {
            x = h1->val;
            h1 = h1->next;
        }
        else {
            x = h2->val;
            h2 = h2->next;
        }
        ListNode *tmp = new ListNode;
        tmp->val = x;
        tmp->next = nullptr;
        now->next = tmp;
        now = now->next;
    }
    if(h1) now->next = h1;
    else now->next = h2;
    return head;
}
int main(){
    ListNode *h1, *h2;
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    h1 = creatList(s1);
    h2 = creatList(s2);
    ListNode *p = mergeList(h1, h2);
    p = p->next;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }
    return 0;
}