劍指Offer面試題：16.合并兩個排序的鏈表
這也是一道出鏡率極高的面試題，我相信很多童鞋都會很眼熟，就像于千萬人之中遇見不期而遇的人，沒有別的話可說,唯有輕輕地問一聲:“哦,原來你也在這里? ”題目：輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的結點仍然是按照遞增排序的。例如輸入下圖中的鏈表1和鏈表2，則合并之后的升序鏈表如鏈表3所示。
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 測試準備
?。?）借助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 測試結果
?。?）測試通過情況
?。?）代碼覆蓋率
浙公網安備 33010602011771號