C++面试宝典第4题：合并链表

题目

有一个链表，其节点声明如下：

struct TNode
{
    int nData;
    struct TNode *pNext;
    TNode(int x) : nData(x), pNext(NULL) {}
};

现给定两个按升序排列的单链表pA和pB，请编写一个函数，实现这两个单链表的合并。合并后，仍然按升序进行排列。比如：单链表pA为1->3->5->6->8，单链表pB为2->3->7，则合并后返回的链表为1->2->3->3->5->6->7->8。函数的声明如下：

TNode *MergeList(TNode *pA, TNode *pB);

解析

这道题主要考察应聘者对链表等数据结构的理解能力，在面试中比较常见。一般有两种解法：一种是使用递归函数来实现，另一种是使用链表遍历来实现。

先来看第一种解法，使用递归函数来实现。当链表pA为NULL时，直接返回链表pB即可。当链表pB为NULL时，直接返回链表pA即可。当链表pA和pB均不为NULL时，则比较链表首部的元素，若pA->nData小于pB->nData，则返回pA，并让pA->pNext指向递归函数MergeList(pA->pNext, pB)的返回值。下面，我们给出了这道题的示例代码。

#include<iostream>
using namespace std;

struct TNode
{
    int nData;
    struct TNode *pNext;
    TNode(int x) : nData(x), pNext(NULL) {}
};

// 插入新节点到链表尾部
TNode *AppendNode(TNode *pTail, int nData)
{  
    TNode *pNodeNew = new TNode(nData);
    pTail->pNext = pNodeNew;
    return pNodeNew;
}

// 打印链表
void PrintList(TNode *pNode)
{
    while (pNode != NULL)
    {
        cout << pNode->nData;
        pNode = pNode->pNext;
        if (pNode != NULL)
        {
            cout << "->";
        }
        else
        {
            cout << endl;
        }
    }
}

// 合并两个链表
TNode *MergeList(TNode *pA, TNode *pB)
{  
    if (pA == NULL)
    {
        return pB;
    }

    if (pB == NULL)
    {
        return pA;
    }

    if (pA->nData < pB->nData)
    {
        pA->pNext = MergeList(pA->pNext, pB);
        return pA;
    }
    else
    {
        pB->pNext = MergeList(pA, pB->pNext);
        return pB;
    }
}  

int main()
{
    TNode *pA = new TNode(1);
    TNode *pTail = AppendNode(pA, 3);
    pTail = AppendNode(pTail, 5);
    pTail = AppendNode(pTail, 6);
    pTail = AppendNode(pTail, 8);
    // 输出：1->3->5->6->8
    PrintList(pA);

    TNode *pB = new TNode(2);
    pTail = AppendNode(pB, 3);
    pTail = AppendNode(pTail, 7);
    // 输出：2->3->7
    PrintList(pB);

    TNode *pResult = MergeList(pA, pB);
    // 输出：1->2->3->3->5->6->7->8
    PrintList(pResult);
    return 0;
}

当然，递归函数也有其缺点：当链表中的元素较多，递归的层级较多时，可能会导致堆栈溢出。

接下来，我们来看第二种解法，使用链表遍历来实现。首先，当链表pA和pB其中一个为NULL时，直接返回另一个链表即可。接下来，我们创建了一个新的临时节点，作为新链表的头和尾，并遍历链表pA和pB。在遍历过程中，如果pA->nData小于pB->nData，则将pA作为新链表尾部的下一个节点，并遍历新链表尾部和pA的下一个节点；如果pA->nData不小于pB->nData，则将pB作为新链表尾部的下一个节点，并遍历新链表尾部和pB的下一个节点。循环遍历完成后，由于链表pA和pB不一样长，因此，需要检查链表pA和pB是否为NULL。若不为NULL，则将对应链表放到新链表尾部。最后，我们返回了新建节点的下一个节点作为合并后的链表首节点，并删除了新建的临时节点。具体实现，可参考如下的示例代码。

#include<iostream>
using namespace std;

struct TNode
{
    int nData;
    struct TNode *pNext;
    TNode(int x) : nData(x), pNext(NULL) {}
};

// 插入新节点到链表尾部
TNode *AppendNode(TNode *pTail, int nData)
{  
    TNode *pNodeNew = new TNode(nData);
    pTail->pNext = pNodeNew;
    return pNodeNew;
}

// 打印链表
void PrintList(TNode *pNode)
{
    while (pNode != NULL)
    {
        cout << pNode->nData;
        pNode = pNode->pNext;
        if (pNode != NULL)
        {
            cout << "->";
        }
        else
        {
            cout << endl;
        }
    }
}

// 合并两个链表
TNode *MergeList(TNode *pA, TNode *pB)
{
    if (pA == NULL)
    {
        return pB;
    }

    if (pB == NULL)
    {
        return pA;
    }

    TNode *pResult = new TNode(-1);
    TNode *pTail = pResult;
    while (pA && pB)
    {
        if (pA->nData < pB->nData)
        {
            pTail->pNext = pA;
            pTail = pTail->pNext;
            pA = pA->pNext;
        } 
        else
        {
            pTail->pNext = pB;
            pTail = pTail->pNext;
            pB = pB->pNext;
        }
    }

    if (pA)
    {
        pTail->pNext = pA;
    }

    if (pB)
    {
        pTail->pNext = pB;
    }

    TNode *pTemp = pResult;
    pResult = pResult->pNext;
    delete pTemp;
    return pResult;
}

int main()
{
    TNode *pA = new TNode(1);
    TNode *pTail = AppendNode(pA, 3);
    pTail = AppendNode(pTail, 5);
    pTail = AppendNode(pTail, 6);
    pTail = AppendNode(pTail, 8);
    // 输出：1->3->5->6->8
    PrintList(pA);

    TNode *pB = new TNode(2);
    pTail = AppendNode(pB, 3);
    pTail = AppendNode(pTail, 7);
    // 输出：2->3->7
    PrintList(pB);

    TNode *pResult = MergeList(pA, pB);
    // 输出：1->2->3->3->5->6->7->8
    PrintList(pResult);
    return 0;
}