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

题目

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

例如，输入图3.11中的链表1和链表2，则合并之后升序链表如链表3所示。

1.png

思路：先合并两条链表，在使用两个指针比较值进行交换结点位置

3.png

分析

• 1、分析两个链表的合并过程

分析从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点是合并后的头结点

• 2、剩余结点的合并

在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面一样。还是比较两个头结点的值。此时链表2的头结点小于链表1的头结点的值，因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。再把这个结点和前面合并链表时得到的链表的尾结点链接起来。

• 3、最后

两个链表剩余的结点依然是排序的，因此合并的步骤和之前的步骤是一样的，这就是典型的递归过程，可以使用递归函数完成

算法实现

#include <iostream>
using namespace std;

struct ListNode {
    int m_nValue;
    ListNode *m_pNext;
};

ListNode* Merge(ListNode *pHead1, ListNode *pHead2)
{
    if (pHead1 == nullptr) {
        return pHead2;
    } else if (pHead2 == nullptr){
        return pHead1;
    }

    ListNode *pMergeHead = nullptr;

    if (pHead1->m_nValue < pHead2->m_nValue) {
        pMergeHead = pHead1;
        pMergeHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
    } else {
        pMergeHead = pHead2;
        pMergeHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
    }

    return pMergeHead;
}

非递归实现

ListNode *Merge2(ListNode *pHead1, ListNode *pHead2) {
    // 新建一个头节点，用来存合并的链表
    ListNode *head = new ListNode();
    head->m_pNext = nullptr;
    ListNode *root = head;
    while (pHead1 != nullptr && pHead2 != nullptr) {
        if (pHead1->m_nValue < pHead2->m_nValue) {
            head->m_pNext = pHead1;
            head = pHead1;
            pHead1 = pHead1->m_pNext;
        } else {
            head->m_pNext = pHead2;
            head = pHead2;
            pHead2 = pHead2->m_pNext;
        }
    }

    // 把未结束的链表连接到合并后的链表尾部
    if (pHead1 != nullptr) {
        head->m_pNext = pHead1;
    } else if (pHead2 != nullptr) {
        head->m_pNext = pHead2;
    }

    return root->m_pNext;
}

参考

《剑指offer》