剑指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 测试结果
（1）测试通过情况
（2）代码覆盖率
正文到此结束
