剑指offer：合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按照递增排序的。

要求：

1、输入的两个链表中有一个或者多个元素相等。

2、输入的链表中有一个或者两个链表都是空链表。

基本思路：

相信大家都知道这题的思路，本题的考点并在在于思路，而在于对链表基本性质的掌握程序，对链表的创建，构造，重置等性质有了一定的了解，求解本题并不难。

对于两个链表，分别有指针指着两个链表的表头，分别比较表头的大小，取小的那一个，然后此链表遍历下一个，直到某一个链表遍历到底，则把另外的没有遍历的链表放在新链表后面就可以了。

下面是本题的源代码：

#include
  
   

typedef struct Link
{
    int key;
    struct Link *next;
}Link;
Link *create(int n)
{
    if(n<=0)
    {
        printf("\n你输入的链表长度不是正整数!\n");
        exit(0);
    }
    else
    {
        Link *node1,*node2,*head;
        head=NULL;
        int i;
        node1=node2=(Link *)malloc(sizeof(Link));
        scanf("%d",&node1->key);
        head=node1;
        node2->next=node1;
        node2=node1;
        for(i=1;i
   
    key); node2->next=node1; node2=node1; } node2->next=NULL; return head; } } Link *mergeLink(Link *head1,Link *head2) { Link *head,*tmp; if(head1->key<=head2->key) { tmp=head1; head1=head1->next; } else { tmp=head2; head2=head2->next; } head=tmp; while(head1!=NULL&&head2!=NULL) { if(head1->key<=head2->key) { tmp->next=head1; tmp=head1; head1=head1->next; } else { tmp->next=head2; tmp=head2; head2=head2->next; } } if(head1!=NULL)tmp->next=head1; if(head2!=NULL)tmp->next=head2; return head; } int main() { int link1,link2; printf("请输入链表1的长度:\n"); scanf("%d",&link1); printf("请输入链表2的长度:\n"); scanf("%d",&link2); Link *head1,*head2,*node1,*node2,*head; head1=create(link1); head2=create(link2); node1=head1; node2=head2; printf("\n输出链表1元素:\n"); while(node1!=NULL) { printf("%d\t",node1->key); node1=node1->next; } printf("\n输出链表2元素:\n"); while(node2!=NULL) { printf("%d\t",node2->key); node2=node2->next; } printf("\n输出合并后的链表:\n"); head=mergeLink(head1,head2); while(head!=NULL) { printf("%d\t",head->key); head=head->next; } return 0; }