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()
}

運行上述代碼，打印結果如下，表明單鏈表反轉成功：

學習過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習社」與學院君討論：

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/t5yZrMSzB_poBe8G3hC-ag

猜你喜歡