《面试准备》C++链表操作3（合并两个有序链表）

#include <iostream>
#include <stack>
using namespace std;

//单向链表节点
struct ListNode{
    int value;
    struct ListNode *Next;
};

class MyList
{
public:
    ListNode *Head1;
    ListNode *Head2;
    ListNode *res;
public:
    MyList(){
        Head1 = new ListNode;
        Head2 = new ListNode;
        res = new ListNode;
    }
    ~MyList(){
        delete Head1;
        Head1 = NULL;
        delete Head2;
        Head2 = NULL;
        delete res;
        res = NULL;
    }
    void creatlist();
    ListNode* conbinelist();
    void bianli();
};

void MyList::creatlist(){
    ListNode *P1 = Head1;
    P1->value = 0;
    //创建Head1
    for(int i = 1;i<=2;i++){
        ListNode *tmp1 = new ListNode;
        tmp1->value = i*3;
        tmp1->Next =NULL;
        P1->Next = tmp1;
        P1 = tmp1;
    }
    ListNode *P2 = Head2;
    P2->value = -1;
    //创建Head2
    for(int j = 1;j<=3;j++){
        ListNode *tmp2 = new ListNode;
        tmp2->value = j+1;
        tmp2->Next =NULL;
        P2->Next = tmp2;
        P2 = tmp2;
    }
}

ListNode* MyList::conbinelist(){
    if(Head1==NULL)
        return Head2;
    if(Head2==NULL)
        return Head1;
    if(Head1->value<=Head2->value){
        res = Head1;
        Head1 = Head1->Next;
    }else{
        res = Head2;
        Head2 = Head2->Next;
    }
    ListNode *Head =res;
    while(Head1!=NULL&&Head2!=NULL){
        if(Head1->value<=Head2->value){
            Head->Next = Head1;
            Head = Head->Next;
            Head1 = Head1->Next;
        }
        else{
            Head->Next = Head2;
            Head = Head->Next;
            Head2 = Head2->Next;
        }
    }
    Head->Next = (Head1==NULL?Head2:Head1);
    return res;
}

void MyList::bianli(){
    ListNode* P =res;
    while(P!=NULL){
        cout<<P->value<<" ";
        P = P->Next;
    }
}
int main ()
{
    MyList *mylist = new MyList;        //自己定义一个对象
    mylist->creatlist();
    mylist->conbinelist();
    mylist->bianli();
    delete mylist;
    mylist = NULL;
    return 0;
}

补充：两个有序数组合并仍然有序（思路一样）： 

#include <iostream>
#include <unordered_map>
using namespace std;


int* conbine(int a[],int b[]){
    int cnt1=0,cnt2=0,n=0;
    static int c[10]={0};　　　//静态变量，在函数结束时不会自动释放
    if(a[0]<=b[0]){
        c[0] = a[0];
        a++;
        cnt1++;
    }
    else{
        c[0] = b[0];
        b++;
        cnt2++;
    }
    while(cnt1<4&&cnt2<6){
        if(*a<=*b){
            c[++n] = *a;
            a++;
            cnt1++;
        }else{
            c[++n] = *b;
            b++;
            cnt2++;
        }
    }
    if(cnt1<4){
        for(int i=cnt1;i<4;i++){
            c[++n] = *a;
            a++;
        }
    }
    if(cnt2<6){
        for(int i=cnt2;i<6;i++){
            c[++n] = *b;
            b++;
        }
    }
    return c;
}

int main(){
    int a[4]={-1,3,5,7};
    int b[6]={-2,0,5,6,8,9};
    int *c = conbine(a,b);
    for(int i=0;i<10;i++){
        cout<<c[i]<<" ";
    }
    return 0;
}

或者进行指针操作：

#include <iostream>
#include <unordered_map>
using namespace std;


int* conbine(int a[],int b[]){
    int cnt1=0,cnt2=0;
    int *c=(int*)malloc(sizeof(int)*10);  //动态分配，在堆中
    if(*a<=*b){
        *c = *a;
        a++;
        cnt1++;
    }
    else{
        *c = *b;
        b++;
        cnt2++;
    }
    int *p = c;
    while(cnt1<4&&cnt2<6){
        if(*a<=*b){
            *(++p) = *a;
            a++;
            cnt1++;
        }else{
            *(++p) = *b;
            b++;
            cnt2++;
        }
    }
    if(cnt1<4){
        for(int i=cnt1;i<4;i++){
            *(++p) = *a;
            a++;
        }
    }
    if(cnt2<6){
        for(int i=cnt2;i<6;i++){
            *(++p) = *b;
            b++;
        }
    }
    return c;
}

int main(){
    int a[4]={-1,3,5,7};
    int b[6]={-2,0,5,6,8,9};
    int *c = conbine(a,b);
    for(int i=0;i<10;i++){
        cout<<c[i]<<" ";
    }
    return 0;
}