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

时间:2023-01-26 19:29:02

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

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

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

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

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

  链表结点定义如下,使用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();
Node node3 = new Node();
Node node5 = new Node(); node1.Next = node3;
node3.Next = node5; Node node2 = new Node();
Node node4 = new Node();
Node node6 = new Node(); node2.Next = node4;
node4.Next = node6; Node newHead = mergeHelper.Merge(node1, node2);
Assert.AreEqual(GetListString(newHead), "");
} // 两个链表中有重复的数字
// list1: 1->3->5
// list2: 1->3->5
[TestMethod]
public void MergeTest2()
{
Node node1 = new Node();
Node node3 = new Node();
Node node5 = new Node(); node1.Next = node3;
node3.Next = node5; Node node2 = new Node();
Node node4 = new Node();
Node node6 = new Node(); node2.Next = node4;
node4.Next = node6; Node newHead = mergeHelper.Merge(node1, node2);
Assert.AreEqual(GetListString(newHead), "");
}

  (2)特殊输入测试

    // 两个链表都只有一个数字
// list1: 1
// list2: 2
[TestMethod]
public void MergeTest3()
{
Node node1 = new Node();
Node node2 = new Node(); Node newHead = mergeHelper.Merge(node1, node2);
Assert.AreEqual(GetListString(newHead), "");
} // 两个链表中有一个空链表
// list1: 1->3->5
// list2: null
[TestMethod]
public void MergeTest4()
{
Node node1 = new Node();
Node node3 = new Node();
Node node5 = new Node(); node1.Next = node3;
node3.Next = node5; Node newHead = mergeHelper.Merge(node1, null);
Assert.AreEqual(GetListString(newHead), "");
} // 两个链表都是空链表
// list1: null
// list2: null
[TestMethod]
public void MergeTest5()
{
Node newHead = mergeHelper.Merge(null, null);
Assert.AreEqual(GetListString(newHead), null);
}

3.3 测试结果

  (1)测试通过情况

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

  (2)代码覆盖率

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

作者:周旭龙

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

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