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