链表合并

#include <bits/stdc++.h>
using namespace std;
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL){}
};
ListNode* createList(vector<int>& nums){
    if(nums.size() == 0)
        return NULL;
    ListNode* head = new ListNode(nums[0]);
    ListNode* curNode = head;
    for(int i = 1; i < nums.size(); ++i){
        curNode->next = new ListNode(nums[i]);
        curNode = curNode->next;
    }
    return head;
}
ListNode* MergeTwoListNode(ListNode* l1, ListNode* l2){
    if(!l1)
        return l2;
    if(!l2)
        return l1;
    if(l1->val < l2->val){
        l1->next = MergeTwoListNode(l1->next, l2);
        return l1;
    }
    else{
        l2->next = MergeTwoListNode(l1, l2->next);
        return l2;
    }
}
int main()
{
    vector<int> nums1, nums2;
    int num1, num2;
    while(cin >> num1)
    {
        nums1.push_back(num1);
        if(cin.get() == '\n')
            break;
    }
    while(cin >> num2)
    {
        nums2.push_back(num2);
        if(cin.get() == '\n')
            break;
    }
    ListNode* head1 = createList(nums1);
    ListNode* head2 = createList(nums2);
    ListNode* res = MergeTwoListNode(head1, head2);
    ListNode* p=res;
    while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    return 0;
}

老实做链表还不如写数组
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums1, nums2,nums;
    int num1, num2;
    while(cin >> num1)
    {
        nums1.push_back(num1);
        nums.push_back(num1);
        if(cin.get() == '\n')
            break;
    }
    while(cin >> num2)
    {
        nums2.push_back(num2);
        nums.push_back(num2);
        if(cin.get() == '\n')
            break;
    }
    sort(nums.begin(),nums.end());
    for(int i=0;i<nums.size();i++)
        cout<<nums[i]<<" ";
    return 0;
}

print(" ".join(strl))

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node* next;
};

node* creatlist(const vector<int> &arr){
    node *head=nullptr,*end=nullptr;
    int index=0;
    if(arr.size()==0)
        return nullptr;
    head=new node;
    head->data=arr[index++];
    end=head;
    while(index<arr.size()){
        node *temp=new node;
        temp->data=arr[index++];
        end->next=temp;
        end=end->next;
    }
    end->next=nullptr;
    return head;
}

node* solve(node *head1,node *head2){
    node *cur1,*cur2;
    if(head1->data<=head2->data){
        cur1=head1;
        cur2=head2;
    }
    else{
        cur1=head2;
        cur2=head1;
    }
    node *newhead=cur1;
    node *next,*pre=nullptr;
    while(cur1&&cur2){
        if(cur1->data <= cur2->data){
            pre=cur1;
            cur1=cur1->next;
        }
        else{
            next=cur2->next;
            pre->next=cur2;
            cur2->next=cur1;
            pre=cur2;
            cur2=next;
        }
    }
    if(cur1==nullptr)
        pre->next=cur2;
    return newhead;
}

int main(){
    vector<int> arr1,arr2;
    while(1){
        int t;
        cin>>t;
        arr1.push_back(t);
        if(cin.get()=='\n')
            break;
    }
    while(1){
        int t;
        cin>>t;
        arr2.push_back(t);
        if(cin.get()=='\n')
            break;
    }
    node *head1,*head2,*head;
    head1=creatlist(arr1);
    head2=creatlist(arr2);
    head=solve(head1,head2);
    while(head){
        cout<<head->data;
        head=head->next;
        if(head)
            cout<<" ";
    }
    return 0;
}

""""
有序链表合并，条件判断
"""
if __name__ == "__main__":
    a = list(map(int, input().strip().split()))
    b = list(map(int, input().strip().split()))
    ans = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            ans.append(a[i])
            i += 1
        else:
            ans.append(b[j])
            j += 1
    ans += a[i:]
    ans += b[j:]
    print(' '.join(map(str, ans)))

	

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> a, b, v;
    int x;
    string s;
    getline(cin,s);
    stringstream ss1(s);
    while(ss1>>x)
        a.push_back(x);
    getline(cin, s);
    stringstream ss2(s);
    while(ss2>>x)
        b.push_back(x);
    int i=0, j=0, n=a.size(), m=b.size();
    while(i<n && j<m){
        if(a[i]<b[j])
            v.push_back(a[i++]);
        else
            v.push_back(b[j++]);
    }
    while(i<n)
        v.push_back(a[i++]);
    while(j<m)
        v.push_back(b[j++]);
    for(int i=0;i<v.size();i++){
        if(i==v.size()-1)
            cout<<v[i]<<endl;
        else
            cout<<v[i]<<" ";
    }
    return 0;
}

import java.util.*;
//链表节点定义
class ListNode{
    int val;
    ListNode next;
    ListNode(int val){this.val = val;}
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ListNode p1 = creatList(sc.nextLine().split(" "));
        ListNode p2 = creatList(sc.nextLine().split(" "));
        ListNode ansHead = mergeTwoLists(p1, p2);
        while(ansHead != null) {
            System.out.print(ansHead.val+" ");
            ansHead = ansHead.next;
        }
    }
    
    //创建链表函数
    public static ListNode creatList(String[] s){
        if(s == null || s.length == 0)
            return null;
        ListNode dummy = new ListNode(0);
        ListNode curNode = dummy;
        for(int i=0; i<s.length; i++) {
            curNode.next = new ListNode(Integer.parseInt(s[i]));
            curNode = curNode.next;
        }
        curNode.next = null;
        return dummy.next;
    }
    //合并链表函数
    public static ListNode mergeTwoLists(ListNode p1, ListNode p2){
        if(p1 == null)
            return p2;
        if(p2 == null)
            return p1;
        if(p1.val < p2.val){
            p1.next = mergeTwoLists(p1.next, p2);
            return p1;
        }else {
            p2.next = mergeTwoLists(p1, p2.next);
            return p2;
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct List {
    int data;
    struct List* next;
};
typedef List* ListPtr;

void
create_list(ListPtr* list_node, int data) {
    ListPtr refer_ptr = (ListPtr)malloc(sizeof(struct List));
    refer_ptr->data = data;
    refer_ptr->next = NULL;

    *list_node = refer_ptr;
}

void
insert_node(ListPtr* list_node, struct List* node) {
    struct List** refer_ptr = list_node;

    while (*refer_ptr)
        refer_ptr = &(*refer_ptr)->next;

    *refer_ptr = node;
    node->next = NULL;
}

void
sort_list_node(ListPtr l1, ListPtr l2, ListPtr* l3) {
    if (l1 == NULL || l2 == NULL)
        return;

    struct List** refer_l3_ptr = l3;
    while (l1 && l2) {
        if (l1->data < l2->data) {
            *refer_l3_ptr = l1;
            l1 = l1->next;
            refer_l3_ptr = &(*refer_l3_ptr)->next;
        }  
        else {
            *refer_l3_ptr = l2;
            l2 = l2->next;
            refer_l3_ptr = &(*refer_l3_ptr)->next;
        }
    }
    while (l1) {
        *refer_l3_ptr = l1;
        l1 = l1->next;
        refer_l3_ptr = &(*refer_l3_ptr)->next;
    }
    while (l2) {
        *refer_l3_ptr = l2;
        l2 = l2->next;
        refer_l3_ptr = &(*refer_l3_ptr)->next;
    }
}

void
print_list(ListPtr* list) {
    struct List** refer_ptr = list;

    while (*refer_ptr) {
        cout << (*refer_ptr)->data << " ";
        refer_ptr = &(*refer_ptr)->next;
    }
    cout << endl;
}

int main(int argc, char** argv) {
    struct List* l1 = NULL;
    struct List* l2 = NULL;

    int data = 0;
    cin >> data;
    create_list(&l1, data);

    while (getchar() == ' ') {
        cin >> data;
        struct List* node = (struct List*)malloc(sizeof(struct List));
        node->data = data;
        insert_node(&l1, node);
    }

    cin >> data;
    create_list(&l2, data);

    while (getchar() == ' ') {
        cin >> data;
        struct List* node = (struct List*)malloc(sizeof(struct List));
        node->data = data;
        insert_node(&l2, node);
    }

    struct List* l3 = NULL;
    sort_list_node(l1, l2, &l3);
    print_list(&l3);

    return 0;
}

package main

import (
    "fmt"
    "os"
    "bufio"
    "sort"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var x int
    arr:=[]int{}
    for{
        _,ok:=fmt.Fscan(in,&x)
        if ok!=nil{
            break
        }
        arr=append(arr,x)
    }
    sort.Ints(arr)
    for _,x:=range arr{
        fmt.Printf("%v ",x)
    }
}

其实很简单，一步一步做就行了，中间的过程实际上是归并排序里面两个序列合为一个的步骤

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a1 = sc.nextLine();
        String a2 = sc.nextLine();
        sc.close();
        String[] aa1 = a1.split(" ");
        String[] aa2 = a2.split(" ");
        List<integer> b1 = new ArrayList<integer>();
        List<integer> b2 = new ArrayList<integer>();
        for(int i=0;i            b1.add(Integer.parseInt(aa1[i]));
        }
        for(int i=0;i            b2.add(Integer.parseInt(aa2[i]));
        }
        int i=0,j=0;
        List<integer> result = new ArrayList<integer>();
        while(i            if(b1.get(i)                result.add(b1.get(i++));
            }else result.add(b2.get(j++));
        }
        if(i==b1.size()){
            while(j                result.add(b2.get(j++));
            }
        }else{
            while(i                result.add(b1.get(i++));
            }
        }
        for(Integer in:result){
            System.out.print(in+" ");
        }
    }
}</integer></integer></integer></integer></integer></integer>

真的有用链表做的嘛？  
#include<iostream>
(720)#include<vector>
#include<stdio.h>

using namespace std;

int main(void){
    int num;
    char c;
    vector<int> v1;
    vector<int> v2;
    
    while (scanf("%d%c", &num, &c) && c != '\n'){
        v1.push_back(num);
    }
    v1.push_back(num);
    while (scanf("%d%c", &num, &c) && c != '\n'){
        v2.push_back(num);
    }
    v2.push_back(num);
    int L1 = v1.size();
    int L2 = v2.size();
    int i = 0;
    int j = 0;
    while (i < L1 && j < L2){
        if (v1[i] <= v2[j]){
            cout<<v1[i]<<" ";
            i++;
        }
        else{
            cout<<v2[j]<<" ";
            j++;
        }
    }
    while (i < L1){
         cout<<v1[i]<<" ";
         i++;
    }
    while (j < L2){
         cout<<v2[j]<<" ";
         j++;
    }
    return 0;
}

import java.util.*;

class ListNode{
    int var;
    ListNode next=null;
    ListNode(int var){
        this.var = var;
    }
}
public class Main{
    
    public static ListNode insertList(ListNode head, int var){
        ListNode q = new ListNode(var);
        ListNode p = head;
        while(p.next != null){
            p = p.next;
        }
        p.next = q;
        p = q;
        return head;
    }
    
    public static ListNode mergeList(ListNode head1, ListNode head2){
        ListNode p = head1.next;
        ListNode q = head2.next;
        ListNode temp = new ListNode(0);
        ListNode t = temp;
        while(p!=null && q!=null){
            
            if(p.var <= q.var){
                t.next = p;
                t = p;
                p = p.next;
            }else{
                t.next = q;
                t = q;
                q = q.next;
            }
        }
        while(p!=null){
            t.next = p;
            t = p;
            p = p.next;
        }
        while(q!=null){
            t.next = q;
            t = q;
            q = q.next;
        }
        return temp;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] s1 = sc.nextLine().split(" ");
        String[] s2 = sc.nextLine().split(" ");
        ListNode list1 = new ListNode(0);
        ListNode list2 = new ListNode(0);
        for(int i = 0; i < s1.length; i++){
            list1 = insertList(list1, Integer.parseInt(s1[i]));
        }
        for(int i = 0; i < s2.length; i++){
            list2 = insertList(list2, Integer.parseInt(s2[i]));
        }
        ListNode merge = mergeList(list1, list2);
        
        while(merge.next != null){
            merge = merge.next;
            System.out.print(merge.var+" ");
        }
        
    }
}

//就本题而言讨巧的写法，转化为整数数组排序输出
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = br.readLine().split(" ");
        String[] str2 = br.readLine().split(" ");
        int[] arr = new int[str1.length+str2.length];
        for(int i = 0;i < str1.length;i++){
            arr[i] = Integer.parseInt(str1[i]);
        }
        for(int j = 0;j < str2.length;j++){
            arr[str1.length+j] = Integer.parseInt(str2[j]);
        }
        Arrays.sort(arr);
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
struct node{
    node* next;
    int data;
    node(int d):data(d),next(NULL){}
};
node* merge(node* p,node* q)
{
    node* ans = NULL;
    node* tail;
    while(p&&q)
    {
        if(p->data>q->data)
        {
            if(!ans)
            {
                ans = new node(q->data);
                tail = ans;
                
            }
            else{
               node* n = new node(q->data);
               tail->next=n;
               tail=tail->next;
            }
            q=q->next;
        }
        else{
             if(!ans)
            {
                ans = new node(p->data);
                tail = ans;
                
            }
            else{
               node* n = new node(p->data);
               tail->next=n;
               tail=tail->next;
            }
            p=p->next;
        }
    }
    if(q)
    {
        tail->next = q;
    }
    if(p)
    {
        tail->next=p;
    }
    return ans;
}
int main()
{
    string s;
    getline(cin,s);
   // cout<<s<<endl;
    s+=' ';
    istringstream is(s);
    int t;
    node* p=NULL;
    node* q;
    node* p1 = NULL;
    node* q1;
    while(is>>t)
    {
        //cout<<t<<endl;
        if(!p)
        {
            p = new node(t);
            q = p;
        }
        else{
            node* n = new node(t);
            q->next = n;
            q=q->next;
        }
    }
    //getchar();
    getline(cin,s);
    //cout<<s<<endl;
    s+=' ';
    istringstream ss(s);
    while(ss>>t)
    {
        if(!p1)
        {
            p1 = new node(t);
            q1 = p1;
        }
        else{
            node* n = new node(t);
            q1->next = n;
            q1=q1->next;
        }
    }
  
   node* res = merge(p,p1);
   
    while(res)
    {
        cout<<res->data<<" ";
        res = res->next;
    }
    
    
    return 0;
}