剑指offer面试题[17]-合并两个排序的链表

布满荆棘的人生 2022-06-13 06:29 140阅读 0赞

## 题目描述 ##

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

常考题：

假设两个链表如下：

链表1:   1  ->  3 \->  5 \-> 7

链表2:   2  ->  4 \-> 6 \->  8

合并后链表3：1  ->  2 -> 3 -> 4 \->  5 -> 6 -> 7 \-> 8

首先分析合并两个链表的过程。我们的分析从合并链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点。

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

当我们得到的链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是有序的，因此合并的步骤和之前的步骤是一样的。这就是**典型的递归过程**。

还需要注意的是代码的鲁棒性问题。每当代码试图访问空指针指向的内存时程序就会崩溃，从而导致鲁棒性问题。在本题中一旦输入空的链表就会引入空的指针，因此我们需要对空链表单独处理。当第一个链表是空链表，也就是它的头结点是一个空指针时，那么把它和第二个链表合并，显然合并的结果就是第二个链表。同样，当输入的第二个链表的头结点是空指针时，我们把它和第一个链表合并得到的结果就是第一个链表。如果两个链表都是空链表，合并的结果就是一个空链表。

**递归的过程对于初学者来说（比如说我）还是比较难想通的，就算有参考代码。（我相信看多了就好了的，刚开始学什么都难）**

这样，先简化两个链表，假设链表如下：

链表1：  1

链表2：  2

对照着下列程序分析，很容易理解，然后逐个增加链表的元素个数进行分析。。。。。。

class Solution \{  
public:  
    ListNode\* Merge(ListNode\* pHead1, ListNode\* pHead2)  
    \{  
        ListNode\* pMergeHead=NULL;  
        if(pHead1==NULL)  
           return pHead2;  
        if(pHead2==NULL)  
           return pHead1;  
        if(pHead1->val<pHead2->val)  
           \{  
              pMergeHead=pHead1;  
              pMergeHead->next=Merge(pHead1->next,pHead2);  
           \}  
        else  
           \{  
              pMergeHead=pHead2;  
              pMergeHead->next=Merge(pHead1,pHead2->next);  
           \}  
        return  pMergeHead;  
    \}  
\};