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

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入下图中的链表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）代码覆盖率

作者：

出处：

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

转载于:https://www.cnblogs.com/edisonchou/p/4771515.html

你可能感兴趣的文章