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();
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）测试通过情况
（2）代码覆盖率
