剑指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 少说一点

想陪你不只一天

多一点 让我

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

哈哈哈哈哈哈哈哈哈 ........................

剑指Offer的学习笔记（C#篇）-- 合并两个排序的链表的相关教程结束。