剑指Offer的学习笔记（C#篇）合并两个排序的链表

题目描述

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

一 . 题目分析

根据题意，可得出，该题目要求两个单增的链表合成一条单增的链表。

链表一：1→5→9→11

链表二：2→4→10→12

新链表为：1→2→4→5→9→10→11→12

二 . 解题思路

定义两个链表的指针；比较两个链表的头结点，让较小的头结点作为新链表的头结点；递归比较两个链表的其余节点，让较小的节点作为上一个新节点的后一个节点。具体实现方法如下：

三 . 代码实现

class Solution
{
    public ListNode Merge(ListNode pHead1, ListNode pHead2)
    {
        // write code here
        //前两部声明当有一个列表为空时，输出另外一个列表：用途，链表中最后一个数的输出
        if (pHead1 == null)
        {
            return pHead2;
        }
        if (pHead2 == null)
        {
            return pHead1;
        }
        //这里定义一个新的空链表，当然不定义也行，随意。；老实说，写多了 ，不过无关紧要
        ListNode newNode = null;
        //两个链表的首数据大小判断，判断结束后，执行递归。
        if (pHead1.val <= pHead2.val)
        {
            newNode = pHead1;
            //Merge即为重新调用该函数，完成递归。递归必须有终结条件，否则即为死循环
            //而该函数的终结条件即为前面开头的那两个if语句。
            newNode.next = Merge(pHead1.next,pHead2);
        }
        else
        {
            newNode = pHead2;
            newNode.next = Merge(pHead1,pHead2.next);
        }
        return newNode;
    }
}

Oh baby 情话多说一点

想我就多看一眼

表现多一点点

让我能真的看见

Oh Bye 少说一点

想陪你不只一天

多一点让我

心甘情愿爱你 -- 好听吗？？