Press "Enter" to skip to content

Go 常见算法面试题篇(一):反转单链表

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

题目

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

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

image-20210802105018671

太烂了有点差凑活看还不错太棒了 (3 人打了分, 平均分: 5.00)
Loading...
发表评论