专栏首页EdisonTalk剑指Offer面试题:16.合并两个排序的链表

剑指Offer面试题:16.合并两个排序的链表

PS:这也是一道出镜率极高的面试题,我相信很多童鞋都会很眼熟,就像于千万人之中遇见不期而遇的人,没有别的话可说,唯有轻轻地问一声:“哦,原来你也在这里? ”

一、题目:合并两个排序的链表

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入下图中的链表1和链表2,则合并之后的升序链表如链表3所示。

  链表结点定义如下,使用C#描述:

    public class Node
    {
        public int Data { get; set; }
        // 指向后一个节点
        public Node Next { get; set; }

        public Node(int data)
        {
            this.Data = data;
        }

        public Node(int data, Node next)
        {
            this.Data = data;
            this.Next = next;
        }
    }

二、解题思路

Step1.定义一个指向新链表的指针,暂且让它指向NULL;

Step2.比较两个链表的头结点,让较小的头结点作为新链表的头结点;

Step3.递归比较两个链表的其余节点,让较小的节点作为上一个新节点的后一个节点;

    public Node Merge(Node head1, Node head2)
    {
        if (head1 == null)
        {
            return head2;
        }
        else if (head2 == null)
        {
            return head1;
        }

        Node newHead = null;

        if (head1.Data <= head2.Data)
        {
            newHead = head1;
            newHead.Next = Merge(head1.Next, head2);
        }
        else
        {
            newHead = head2;
            newHead.Next = Merge(head1, head2.Next);
        }

        return newHead;
    }

三、单元测试

3.1 测试准备

  (1)借助MSUnit框架进行初始化与清理工作[TestInitialize]与[TestCleanup]

    private MergeHelper mergeHelper;

    [TestInitialize]
    public void Initialize()
    {
        // 实例化
        mergeHelper = new MergeHelper();
    }

    [TestCleanup]
    public void CleanUp()
    {
        // 不用TA了
        mergeHelper = null;
    } 

  (2)封装一个便于测试对比的辅助方法,将新链表生成一个字符串用于对比

    public string GetListString(Node head)
    {
        if (head == null)
        {
            return null;
        }

        StringBuilder sbList = new StringBuilder();
        while (head != null)
        {
            sbList.Append(head.Data.ToString());
            head = head.Next;
        }

        return sbList.ToString();
    } 

3.2 测试用例

  (1)功能测试

    // list1: 1->3->5
    // list2: 2->4->6
    [TestMethod]
    public void MergeTest1()
    {
        Node node1 = new Node(1);
        Node node3 = new Node(3);
        Node node5 = new Node(5);

        node1.Next = node3;
        node3.Next = node5;

        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node6 = new Node(6);

        node2.Next = node4;
        node4.Next = node6;

        Node newHead = mergeHelper.Merge(node1, node2);
        Assert.AreEqual(GetListString(newHead), "123456");
    }

    // 两个链表中有重复的数字
    // list1: 1->3->5
    // list2: 1->3->5
    [TestMethod]
    public void MergeTest2()
    {
        Node node1 = new Node(1);
        Node node3 = new Node(3);
        Node node5 = new Node(5);

        node1.Next = node3;
        node3.Next = node5;

        Node node2 = new Node(1);
        Node node4 = new Node(3);
        Node node6 = new Node(5);

        node2.Next = node4;
        node4.Next = node6;

        Node newHead = mergeHelper.Merge(node1, node2);
        Assert.AreEqual(GetListString(newHead), "113355");
    } 

  (2)特殊输入测试

    // 两个链表都只有一个数字
    // list1: 1
    // list2: 2
    [TestMethod]
    public void MergeTest3()
    {
        Node node1 = new Node(1);
        Node node2 = new Node(2);

        Node newHead = mergeHelper.Merge(node1, node2);
        Assert.AreEqual(GetListString(newHead), "12");
    }

    // 两个链表中有一个空链表
    // list1: 1->3->5
    // list2: null
    [TestMethod]
    public void MergeTest4()
    {
        Node node1 = new Node(1);
        Node node3 = new Node(3);
        Node node5 = new Node(5);

        node1.Next = node3;
        node3.Next = node5;

        Node newHead = mergeHelper.Merge(node1, null);
        Assert.AreEqual(GetListString(newHead), "135");
    }

    // 两个链表都是空链表
    // list1: null
    // list2: null
    [TestMethod]
    public void MergeTest5()
    {
        Node newHead = mergeHelper.Merge(null, null);
        Assert.AreEqual(GetListString(newHead), null);
    } 

3.3 测试结果

  (1)测试通过情况

  (2)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer面试题:31.两个链表的第一个公共节点

      碰到这道题,很多人的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和...

    Edison Zhou
  • 剑指Offer面试题:14.链表的倒数第k个节点

    PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善。

    Edison Zhou
  • 剑指Offer面试题:15.反转链表

      由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次...

    Edison Zhou
  • Node.js 基础

    梨涡浅笑
  • 剑指Offer面试题:31.两个链表的第一个公共节点

      碰到这道题,很多人的第一反应就是蛮力法:在第一链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和...

    Edison Zhou
  • 第一章:NodeJS 概述

    Node 概述 什么是 Node Node.js® is a JavaScript runtime built on Chrome's V8 JavaScrip...

    老马
  • 【专业技术】Node.js 究竟是什么?

    简介 如果您听说过 Node,或者阅读过一些文章,宣称 Node 是多么多么的棒,那么您可能会想:“Node 究竟是什么东西?” 即便是在参阅 Node 的主页...

    程序员互动联盟
  • 深入浅出 Nodejs ( 一 ) :Nodejs 的简介

    我认为 Node 是一门独具风格的技术,它的特点很有意思,本章我们主要讲 Node 的特点,Node 应用场景以及 Node 的使用者。

    serena
  • 按深度打印二叉树节点数据

    之前去面试,被问到了一个关于二叉树的问题,本身对算法并不擅长,结果想了半天没想出解决方法,经过面试官提点,才恍然大悟,回来后立马把实现写了出来,详见如下...

    RedSheep
  • Node 10 新功能概览(译)

    以代号“Dubnium”为代表的Node 10于2018年4月24日发布,并将于2018年10月进入长期支持(LTS)。JavaScript开发人员一直在激动地...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券