剑指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）代码覆盖率
正文到此结束
