Go 常見算法面試題篇（一）：反轉(zhuǎn)單鏈表
上周周末有人和我交流反轉(zhuǎn)單鏈表的實現(xiàn)代碼，正好我也要寫常見算法面試題系列，就著這個機(jī)會開始這個系列，和數(shù)據(jù)結(jié)構(gòu)和算法系列并行，以便學(xué)以致用。
題目
那就從反轉(zhuǎn)單鏈表開始吧，這個題目來自《劍指 Offer》這本書，原題如下：
定義一個函數(shù)，輸入一個單鏈表的頭結(jié)點，反轉(zhuǎn)該單鏈表并輸出反轉(zhuǎn)后單鏈表的頭結(jié)點。
對于雙向鏈表來說，顯然不存在反轉(zhuǎn)的問題，因為它有前驅(qū)結(jié)點和后驅(qū)結(jié)點，所以我們限制了條件為單鏈表。
核心思路
要反轉(zhuǎn)一個單鏈表并不難，可以參考雙向鏈表的實現(xiàn)，在遍歷單鏈表的過程中，記錄當(dāng)前結(jié)點為下一個結(jié)點的前驅(qū)結(jié)點，對于頭結(jié)點而言，前驅(qū)結(jié)點為空，然后在遍歷到下一個結(jié)點時，將上一步設(shè)置的前驅(qū)結(jié)點作為該結(jié)點的后驅(qū)結(jié)點，依次類推，直到遍歷到尾結(jié)點（后驅(qū)結(jié)點為空的結(jié)點是尾結(jié)點），再把尾結(jié)點拷貝為反轉(zhuǎn)后單鏈表的頭結(jié)點并返回即可：
實現(xiàn)代碼
有了以上的思路，我們編寫對應(yīng)的 Go 實現(xiàn)代碼如下，在編寫過程中，要關(guān)注代碼魯棒性，比如鏈表為空，包含一個結(jié)點以及包含多個結(jié)點情況如何處理：
package mainimport "fmt"type Node struct {data interface{}next *Node}// 反轉(zhuǎn)單鏈表func (head *Node) reverse() *Node {// 空鏈表if head == nil {return nil}var reverseHead *Node // 反轉(zhuǎn)后單鏈表的頭結(jié)點var preNode *NodecurNode := headfor curNode != nil {nextNode := curNode.nextif nextNode == nil {reverseHead = curNode // 尾結(jié)點轉(zhuǎn)換為頭結(jié)點}// 反轉(zhuǎn)實現(xiàn)，當(dāng)前結(jié)點的前驅(qū)結(jié)點變成后驅(qū)結(jié)點curNode.next = preNode// 設(shè)置下一個結(jié)點的前驅(qū)結(jié)點preNode = curNodecurNode = nextNode}// 返回反轉(zhuǎn)后的頭結(jié)點return reverseHead}
最后編寫一段測試代碼驗證單鏈表反轉(zhuǎn)是否成功：
// 遍歷單鏈表func (head *Node) traverse() {node := headfor 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 = secondsecond.next = thirdhead := firstfmt.Print("反轉(zhuǎn)前: ")head.traverse()fmt.Println()newHead := head.reverse()fmt.Print("反轉(zhuǎn)后: ")newHead.traverse()fmt.Println()}
運行上述代碼，打印結(jié)果如下，表明單鏈表反轉(zhuǎn)成功：
（本文完）
學(xué)習(xí)過程中有任何問題，可以通過下面的評論功能或加入「Go 語言研習(xí)社」與學(xué)院君討論：
本系列教程首發(fā)在 geekr.dev，你可以點擊頁面左下角閱讀原文鏈接查看最新更新的教程。