Go 常见算法面试题篇（一）：反转单链表

原创 xueyuanjun 极客书房

上周周末有人和我交流反转单链表的实现代码，正好我也要写常见算法面试题系列，就着这个机会开始这个系列，和数据结构和算法系列并行，以便学以致用。

题目

那就从反转单链表开始吧，这个题目来自《剑指 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()}

运行上述代码，打印结果如下，表明单链表反转成功：

继续滑动看下一个