合并两条排序的链表详解编程语言

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。例如，输入图1中的链表1和链表2，则合并之后的升序链表如链表3所示。链表节点定义如下：

typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode;

图1：合并两个排序链表的过程

【解题思路】
已知有两条链表，合并成一条新链表，所以定义一个指针（mergephead）指向新链表。
本题用递归方法解决。首先，判断两条链表的情况（空链表和多个节点），再判断两条链表头节点值的大小，以作为递归的条件，最后返回新链表。

【代码】

Node* MergeList(pList phead1, pList phead2) 
{ 
    if (phead1 == NULL) 
    { 
        return phead2; 
    } 
    else if (phead2 == NULL) 
    { 
        return phead1; 
    } 
 
    pNode mergephead = NULL; 
    if (phead1->data < phead2->data) 
    { 
        mergephead = phead1; 
        mergephead->next = MergeList(phead1->next, phead2); 
    } 
    else 
    { 
        mergephead = phead2; 
        mergephead->next = MergeList(phead1, phead2->next); 
    } 
    return  mergephead; 
}

【程序】

#define _CRT_SECURE_NO_WARNINGS 1 
#define _CRT_SECURE_NO_WARNINGS 1 
# include <stdio.h> 
# include <stdlib.h> 
# include <assert.h> 
 
typedef int DataType; 
 
typedef struct Node 
{ 
    DataType data; 
    struct Node *next; 
}Node, *pList, *pNode; 
 
void InitLinkList(pList *pplist) 
{ 
    assert(pplist); 
    *pplist = NULL; 
} 
 
void PushBack(pList *pplist, DataType x) 
{ 
    pNode cur = *pplist; 
    pNode pnode = NULL; 
    assert(pplist); 
    pnode = (pNode)malloc(sizeof(Node)); 
    if (pnode == NULL) 
    { 
        perror("PushBack::malloc"); 
        exit(EXIT_FAILURE); 
    } 
    pnode->data = x; 
    pnode->next = NULL; 
    if (cur == NULL) 
    { 
        *pplist = pnode; 
    } 
    else 
    { 
        while (cur->next != NULL) 
        { 
            cur = cur->next; 
        } 
        cur->next = pnode; 
    } 
} 
 
void Display(pList plist) 
{ 
    pNode cur = plist; 
    while (cur) 
    { 
        printf("%d-->", cur->data); 
        cur = cur->next; 
    } 
    printf("over/n"); 
} 
 
void Destroy(pList *pplist) 
{ 
    pNode cur = *pplist; 
    assert(pplist); 
    while (cur) 
    { 
        pNode del = cur; 
        cur = cur->next; 
        free(del); 
    } 
    *pplist = NULL; 
} 
 
Node* MergeList(pList phead1, pList phead2) 
{ 
    if (phead1 == NULL) 
    { 
        return phead2; 
    } 
    else if (phead2 == NULL) 
    { 
        return phead1; 
    } 
 
    pNode mergephead = NULL; 
    if (phead1->data < phead2->data) 
    { 
        mergephead = phead1; 
        mergephead->next = MergeList(phead1->next, phead2); 
    } 
    else 
    { 
        mergephead = phead2; 
        mergephead->next = MergeList(phead1, phead2->next); 
    } 
    return  mergephead; 
} 
 
void test1() 
{ 
    pList plist; 
    pList plist1; 
    pList plist2; 
    pNode ret = NULL; 
    InitLinkList(&plist); 
    InitLinkList(&plist1); 
    InitLinkList(&plist2); 
    PushBack(&plist1, 1); 
    PushBack(&plist1, 3); 
    PushBack(&plist1, 5); 
    PushBack(&plist1, 7); 
    Display(plist1); 
    PushBack(&plist2, 2); 
    PushBack(&plist2, 4); 
    PushBack(&plist2, 6); 
    PushBack(&plist2, 8); 
    Display(plist2); 
    plist = MergeList(plist1, plist2); 
    Display(plist); 
    Destroy(&plist); 
} 
 
int main() 
{ 
    test1(); 
    system("pause"); 
    return 0; 
}

运行结果为：

【测试】
1、功能测试：
1）输入的链表有多个节点；
2）节点的值互不相同或者存在值相等的多个节点。
2、特殊输入测试：
1）两条链表的一个或者两个头节点为NULL指针；
2）两条链表中只有一个节点。