合并两个排序的链表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
(hint: 请务必使用链表。)

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为两个整数n和m(0<=n<=1000, 0<=m<=1000)：n代表将要输入的第一个链表的元素的个数,m代表将要输入的第二个链表的元素的个数。
下面一行包括n个数t(1<=t<=1000000)：代表链表一中的元素。接下来一行包含m个元素，s(1<=t<=1000000)。

输出：

对应每个测试案例，
若有结果，输出相应的链表。否则，输出NULL。

样例输入：

5 2
1 3 5 7 9
2 4
0 0

样例输出：

1 2 3 4 5 7 9
NULL

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node {
    int data;
    struct node *next;
} linklist;
 
linklist *joinList(linklist *L1, linklist *L2) {
    linklist *pNext1 = L1->next, *pNext2 = L2->next;
    if (pNext1 == NULL && pNext2 == NULL) {
        return NULL;
    }
    else if (pNext2 == NULL) {
        return L1;
    }
    else if (pNext1 == NULL) {
        return L2;
    }
    else {
        linklist *L, *tail;
        L = (linklist *) malloc(sizeof(linklist));
        L->next = NULL;
        tail = L;
 
        while (pNext1 || pNext2) {
            if (pNext1 && pNext2) {
                if (pNext1->data < pNext2->data) {
                    tail->next = pNext1;
                    tail = pNext1;
                    pNext1 = pNext1->next;
                }
                else {
                    tail->next = pNext2;
                    tail = pNext2;
                    pNext2 = pNext2->next;
                }
            }
            else if (pNext1 && !pNext2) {
                tail->next = pNext1;
                tail = pNext1;
                pNext1 = pNext1->next;
            }
            else if (pNext2 && !pNext1) {
                tail->next = pNext2;
                tail = pNext2;
                pNext2 = pNext2->next;
            }
        }
        return L;
    }
}
 
int main() {
    int i, n, m, v;
    linklist *L1, *L2, *tail1, *tail2, *p;
    while (scanf("%d %d", &n, &m) != EOF) {
        L1 = (linklist *) malloc(sizeof(linklist));
        L2 = (linklist *) malloc(sizeof(linklist));
        tail1 = L1;
        tail2 = L2;
        L1->next = NULL;
        L2->next = NULL;
 
        for (i = 0; i < n; i++) {
            scanf("%d", &v);
            p = (linklist *) malloc(sizeof(linklist));
            p->data = v;
            p->next = NULL;
            tail1->next = p;
            tail1 = p;
        }
 
        for (i = 0; i < m; i++) {
            scanf("%d", &v);
            p = (linklist *) malloc(sizeof(linklist));
            p->data = v;
            p->next = NULL;
            tail2->next = p;
            tail2 = p;
        }
 
        L1 = joinList(L1, L2);
 
        if (!L1) {
            printf("NULL\n");
        }
        else {
            p = L1->next;
            while (p) {
                if (!p->next) {
                    printf("%d\n", p->data);
                } else {
                    printf("%d ", p->data);
                }
                p = p->next;
            }
        }
 
        free(p);
        p = NULL;
        free(L1);
        L1 = NULL;
        free(L2);
        L2 = NULL;
 
    }
    return 0;
}
 
/**************************************************************
    Problem: 1519
    User: wusuopuBUPT
    Language: C
    Result: Accepted
    Time:240 ms
    Memory:4080 kb
****************************************************************/

合并两个排序的链表

原文：http://blog.csdn.net/wusuopubupt/article/details/18364087