Press "Enter" to skip to content

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

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

题目

那就从反转单链表开始吧,这个题目来自《剑指 Offer》这本书,原题如下:

定义一个函数,输入一个单链表的头结点,反转该单链表并输出反转后单链表的头结点。

对于双向链表来说,显然不存在反转的问题,因为它有前驱结点和后驱结点,所以我们限制了条件为单链表。

核心思路

要反转一个单链表并不难,可以参考双向链表的实现,在遍历单链表的过程中,记录当前结点为下一个结点的前驱结点,对于头结点而言,前驱结点为空,然后在遍历到下一个结点时,将上一步设置的前驱结点作为该结点的后驱结点,依次类推,直到遍历到尾结点(后驱结点为空的结点是尾结点),再把尾结点拷贝为反转后单链表的头结点并返回即可。

实现代码

有了以上的思路,我们编写对应的 Go 实现代码如下,在编写过程中,要关注代码鲁棒性,比如链表为空,包含一个结点以及包含多个结点情况如何处理:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
}
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 }
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
}

最后编写一段测试代码验证单链表反转是否成功:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 遍历单链表
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()
}
// 遍历单链表 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() }
// 遍历单链表
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

发表回复