劍指Offer面試題：15.反轉鏈表
題目：定義一個函數，輸入一個鏈表的頭結點，反轉該鏈表并輸出反轉后鏈表的頭結點。由于題目并沒有要求必須原地反轉，因此可以借助外部空間實現。這里可以將單鏈表儲存為數組，然后按照數組的索引逆序進行反轉。但是，此方式比較浪費空間，而且需要兩次遍歷，效率不占優勢。
一、題目：反轉鏈表
題目：定義一個函數，輸入一個鏈表的頭結點，反轉該鏈表并輸出反轉后鏈表的頭結點。
鏈表結點定義如下，這里使用的是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; } }
二、解題思路
2.1 借助外部空間的解法一
由于題目并沒有要求必須原地反轉，因此可以借助外部空間實現。這里可以將單鏈表儲存為數組，然后按照數組的索引逆序進行反轉。但是，此方式比較浪費空間，而且需要兩次遍歷，效率不占優勢。
依據上面的思路，我們可以寫出以下代碼：
public static Node ReverseList1(Node head) { if(head == null) { return null; } List<Node> nodeList = new List<Node>(); while (head != null) { nodeList.Add(head); head = head.Next; } int startIndex = nodeList.Count - 1; for (int i = startIndex; i >= 0; i--) { Node node = nodeList[i]; if (i == 0) { node.Next = null; } else { node.Next = nodeList[i - 1]; } } // 現在頭結點是原來的尾節點 head = nodeList[startIndex]; return head; }
2.2 使用三個指針的高效解法二
定義3個指針，分別指向當前遍歷到的結點、它的前一個結點及后一個結點。在遍歷過程中，首先記錄當前節點的后一個節點，然后將當前節點的后一個節點指向前一個節點，其次前一個節點再指向當前節點，最后再將當前節點指向最初記錄的后一個節點，如此反復，直到當前節點的后一個節點為NULL時，則代表當前節點時反轉后的頭結點了。
整個過程只需遍歷鏈表一次，效率提高不少，且需要的外部空間也較第一種方法要少很多，實現代碼如下：
public static Node ReverseList2(Node head) { if (head == null) { return null; } Node reverseHead = null; // 指針1：當前節點 Node currentNode = head; // 指針2：當前節點的前一個節點 Node prevNode = null; while(currentNode != null) { // 指針3：當前節點的后一個節點 Node nextNode = currentNode.Next; if(nextNode == null) { reverseHead = currentNode; } // 將當前節點的后一個節點指向前一個節點 currentNode.Next = prevNode; // 將前一個節點指向當前節點 prevNode = currentNode; // 將當前節點指向后一個節點 currentNode = nextNode; } return reverseHead; }
三、單元測試
3.1 測試用例
（1）為了方便對比，封裝了一個用于將鏈表所有元素輸出為字符串的方法GetNodeString()
// 輔助方法：生成鏈表元素的字符串用于對比 public string GetNodeString(Node head) { if (head == null) { return null; } StringBuilder sbResult = new StringBuilder(); Node temp = head; while (temp != null) { sbResult.Append(temp.Data.ToString()); temp = temp.Next; } return sbResult.ToString(); }
（2）功能測試、特殊輸入測試
// 01.輸入的鏈表有多個結點 [TestMethod] public void ReverseTest1() { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); node1.Next = node2; node2.Next = node3; node3.Next = node4; node4.Next = node5; Node newHead = ListHelper.ReverseList2(node1); Assert.AreEqual(GetNodeString(newHead), "54321"); } // 02.輸入的鏈表只有一個結點 [TestMethod] public void ReverseTest2() { Node node1 = new Node(1); Node newHead = ListHelper.ReverseList2(node1); Assert.AreEqual(GetNodeString(newHead), "1"); } // 03.輸入NULL [TestMethod] public void ReverseTest3() { Node newHead = ListHelper.ReverseList2(null); Assert.AreEqual(GetNodeString(newHead), null); }
3.2 測試結果
?。?）測試通過情況
?。?）代碼覆蓋率
浙公網安備 33010602011771號