两个有序链表序列的合并

（最下边有完整代码及运行截图，中间部分仅提供思路，有残缺）

具体问题如下图所示

简单说一下思路

首先是常规定义一下单链表

#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct Node
{
    int data;
    struct Node* next;
}Node;

然后是将输入的数列存入链表中

创建一个head节点，head的指针域设为NULL，并用L指针指向head。

建立一个循环：在循环内接收输入的序列值（假设为） [ 1 2 3 4 5 -1] （用空格隔开），第一次循环，新建一个节点Node，并让L->next（此时L代表head）指向该新建节点Node，形成链表，其中Node数据域data存入1。按此操作依次进行，直到序列值-1

序列值=-1时，L指向的节点的指针域指向NULL，完成单链表

Node* PutL()
{
    Node head;
    Node* L= &head;
    head.next = NULL;
    int n;
    while (1)
    {
        scanf("%d", &n);
        if (n != -1)
        {
            L->next = (Node*)malloc(sizeof(Node));
            L->next->data = n;
            L = L->next;
        }
        else
            break;
    }
    L->next = NULL;
    return head.next;
}

 然后就是最重要的合并功能

要合并单链表L1和单链表L2，我们首先定义一个空的链表L3

然后我们考虑如何将L1和L2的值如何放进L3

合并时要有这个思路

1.假设输入两个有序数列

 2.再加上对应指针，首先指向对应序列的头一个节点

 

 3.开始比较对应的值，输出较小的那一个（按题目要求

4.N1输出，将N1指向下一位，L3第一个节点data域等于1

 接着比较N1，N2

5.N2输出后，将N2指向下一位，L3第二个节点data域等于2

 接着比较N1，N2

 如此循环下去

若L1与L2长度不等时

易知L2肯定先输出完，即N2最先指向链表尾部，此时N1指向7，则将N1指向的节点包括后面的全部连接到L3即可 

当然此题并没有严格要求存入新链表，我们当场输出打印即可

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct Node
{
    int data;
    struct Node* next;
}Node;
 
Node* PutL()
{
    Node head;
    Node* L= &head;
    head.next = NULL;
    int n;
    while (1)
    {
        scanf("%d", &n);
        if (n != -1)
        {
            L->next = (Node*)malloc(sizeof(Node));
            L->next->data = n;
            L = L->next;
        }
        else
            break;
    }
    L->next = NULL;
    return head.next;
}
 
 
int main()
{
  Node* L1 = PutL();
    Node* L2 = PutL();
 
int f=0;//处理空格
while (L1&&L2)//两个链表都非空
    {
        if (L1->data > L2->data)//判断首源节点的data的大小
        {
            if (f)
                printf(" ");//当f=0时，进入else；f=1时输出空格
            else
                f = 1;
           printf( "%d",L2->data);
            L2 = L2->next;
        }
        else
        {
            if (f)
                printf(" ");
            else
                f = 1;
            printf("%d",L1->data);
            L1 = L1->next;
        }
    }
    while (L1)//当L1有剩余时
    {
        if (f)
            printf(" ");
        else
            f = 1;
        printf("%d",L1->data);
        L1 = L1->next;
    }
    while (L2)//当L2有剩余时
    {
        if (f)
            printf(" ");
        else
            f = 1;
        printf("%d",L2->data);
        L2 = L2->next;
    }
    if (f == 0)
        printf("NULL");//当f=0时，就证明没有进入任何一个循环，即新链表为空
    return 0;
}