C++实现合并两个已经排序的链表

/*
 * 合并两个已经排序的链表.cpp
 *
 *  Created on: 2018年4月11日
 *      Author: soyo
 */
#include<iostream>
using namespace std;
struct Node{
    int num;
    Node * next;
};
Node * creat(int x)
{
    Node *head;
    Node *p;
    head=new Node;
    p=head;
    p->num=x;
    p->next=NULL;
   return head;
}
Node * insert(Node*head,int data)
{
    Node *p1,*p;
    p1=new Node;
    p1->num=data;
    p1->next=NULL;
     p=head;
     while(p->next!=NULL)
     {
         p=p->next;
     }
     p->next=p1;
     return head;
}
void printl(Node *head)
{
      Node *p=head;
      while(p!=NULL)
      {
          cout<<"数据为:"<<p->num;
          p=p->next;
      }
      cout<<endl;
}
Node *Merge(Node*head1,Node*head2)
{
    if(head1==NULL)
        return head2;
    else if(head2==NULL)
        return head1;
    Node *newHead=NULL;
    if(head1->num<head2->num)
    {
        newHead=head1;
        newHead->next=Merge(head1->next,head2);
    }
    else
    {
        newHead=head2;
        newHead->next=Merge(head1,head2->next);
    }
    return newHead;
}

int main()
{
     Node *head=creat(1);
      // cout<<head->num<<endl;
       int i;
       int a[]={3,5,7,9};
       for(i=0;i<sizeof(a)/sizeof(int);i++)
       {
           head=insert(head,a[i]);
       }
       printl(head);
       Node *head2=creat(2);
        int b[]={4,6,8,10};
       for(i=0;i<sizeof(a)/sizeof(int);i++)
       {
           head2=insert(head2,b[i]);
       }
       printl(head2);
       Node *newMergeHead;
       newMergeHead=Merge(head,head2);
       printl(newMergeHead);
}

结果：

数据为:1数据为:3数据为:5数据为:7数据为:9
数据为:2数据为:4数据为:6数据为:8数据为:10
数据为:1数据为:2数据为:3数据为:4数据为:5数据为:6数据为:7数据为:8数据为:9数据为:10