题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
链表结点定义如下,这里使用的是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;
}
}
由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势。
依据上面的思路,我们可以写出以下代码:
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;
}
定义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;
}
(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);
}
(1)测试通过情况
(2)代码覆盖率
作者:周旭龙
出处:http://edisonchou.cnblogs.com
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。