上周周末有人和我交流反转单链表的实现代码，正好我也要写常见算法面试题系列，就着这个机会开始这个系列，和数据结构和算法系列并行，以便学以致用。
题目
那就从反转单链表开始吧，这个题目来自《剑指 Offer》这本书，原题如下：
定义一个函数，输入一个单链表的头结点，反转该单链表并输出反转后单链表的头结点。
对于双向链表来说，显然不存在反转的问题，因为它有前驱结点和后驱结点，所以我们限制了条件为单链表。
核心思路
要反转一个单链表并不难，可以参考双向链表的实现，在遍历单链表的过程中，记录当前结点为下一个结点的前驱结点，对于头结点而言，前驱结点为空，然后在遍历到下一个结点时，将上一步设置的前驱结点作为该结点的后驱结点，依次类推，直到遍历到尾结点（后驱结点为空的结点是尾结点），再把尾结点拷贝为反转后单链表的头结点并返回即可。
实现代码
有了以上的思路，我们编写对应的 Go 实现代码如下，在编写过程中，要关注代码鲁棒性，比如链表为空，包含一个结点以及包含多个结点情况如何处理：
package main
import "fmt"
type Node struct {
data interface{}
next *Node
}
// 反转单链表
func (head *Node) reverse() *Node {
// 空链表
if head == nil {
return nil
}
var reverseHead *Node // 反转后单链表的头结点
var preNode *Node
curNode := head
for curNode != nil {
nextNode := curNode.next
if nextNode == nil {
reverseHead = curNode // 尾结点转换为头结点
}
// 反转实现，当前结点的前驱结点变成后驱结点
curNode.next = preNode
// 设置下一个结点的前驱结点
preNode = curNode
curNode = nextNode
}
// 返回反转后的头结点
return reverseHead
}
最后编写一段测试代码验证单链表反转是否成功：
// 遍历单链表
func (head *Node) traverse() {
node := head
for node != nil {
fmt.Printf("%v ", node.data)
node = node.next
}
}
func main() {
first := &Node{data: 1}
second := &Node{data: 2}
third := &Node{data: 3}
first.next = second
second.next = third
head := first
fmt.Print("反转前: ")
head.traverse()
fmt.Println()
newHead := head.reverse()
fmt.Print("反转后: ")
newHead.traverse()
fmt.Println()
}
运行上述代码，打印结果如下，表明单链表反转成功：
