Go 常見算法面試題篇：在 O-1- 時間內刪除單鏈表結點

題目

繼續看一個來自《劍指 Offer》的鏈表題：

給定單向鏈表的頭指針和結點指針，定義一個函數在 O(1) 時間內刪除該結點。

我們知道，單向鏈表刪除一個結點，通常的做法是從鏈表的頭結點開始，順序查找所有結點，直到找到要刪除的結點並刪除，因此，長度爲 n 的鏈表刪除結點的整體時間複雜度是 O(n)，但是題目要求時間複雜度爲 O(1)，該怎麼實現呢？在繼續往下看之前，你不妨先想一想，看看有沒有思路。

如果你對單向鏈表的概念不太熟悉，可以翻到前面的鏈表教程去複習下。

核心思路

按照傳統的思路，刪除一個單鏈表的時間複雜度是 O(n)，之所以要從頭指針開始遍歷，是爲了找到被刪除結點的前驅結點，然後將前驅結點的指針指向被刪除結點的下一個結點，從而完成刪除結點的工作。

但是細想一下，這個時間複雜度是可以優化的，在這個題目中，我們已經知道被刪除結點的信息，這樣就可以獲知被刪除結點的下一個結點，要完成刪除工作，只需要把下一個結點的值複製到待刪除結點，然後把待刪除結點的指針指向下一個結點指針指向的結點，這樣一來，也就達成了刪除待刪除結點的目的，這個思路是不是很巧妙？

其實，這個思路在前面介紹平衡二叉樹節點刪除實現的時候也用到過，知識積累到一定程度，都是觸類旁通的。

顯然，這種只需要獲取待刪除結點的下一個結點的時間複雜度是 O(1)。不過我們考慮問題還要全面：如果待刪除結點是頭結點或者中間結點，存在下一個結點的情況下可以這麼做；如果待刪除結點是尾結點，沒有下一個結點呢？這個時候還是要按照遍歷所有結點的思路找到前驅結點來做。在這種極端情況下，時間複雜度仍然是 O(n)，不過這只是極端特殊情況，就整體平均而言，時間複雜度就是 O(1)。

實現代碼

有了上面的思路，寫起實現代碼來也就簡單了。爲了提升代碼複用率，我們將單鏈表反轉教程中編寫的單鏈表節點類和遍歷方法抽取到獨立的 Go 文件 linked_list.go：

package main

import (
    "fmt"
)

// Node 單鏈表結點類
type Node struct {
    data interface{}
    next *Node
}

// 遍歷單鏈表
func (head *Node) traverse() {
    node := head
    for node != nil {
        fmt.Printf("%v ", node.data)
        node = node.next
    }
}

然後在同級目錄下創建一個 delete.go 定義結點刪除方法：

// 在 O(1) 時間內刪除單鏈表結點
// Author: 學院君
package main

import (
    "errors"
    "fmt"
)

// 刪除指定單鏈表節點
func (head *Node) delete(node *Node) error {
    if head == nil || node == nil {
        return errors.New("鏈表或待刪除結點爲空")
    }
    // 如果待刪除結點是尾結點，還是要遍歷所有結點，此時時間複雜度是 O(n)
    if node.next == nil {
        preNode := head
        for preNode.next != node {
            preNode = preNode.next
        }
        // 找到待刪除結點的前驅結點，將指針置空
        preNode.next = nil
        return nil
    }

    // 如果待刪除結點是頭結點，處理最簡單，此時時間複雜度爲 O(1)
    if node == head {
        head.next = nil
        return nil
    }

    // 既不是頭結點也不是尾結點
    // 將後驅結點值和指針拷貝給待刪除結點，再將下一個結點刪除，此時時間複雜度爲 O(1)
    nextNode := node.next
    node.data = nextNode.data
    node.next = nextNode.next
    return nil
}

最後編寫一段測試代碼，驗證刪除結點是否成功：

func main() {
    // 初始化鏈表結構
    firstNode := &Node{data: 0}
    secondNode := &Node{data: 1}
    firstNode.next = secondNode
    thirdNode := &Node{data: 2}
    secondNode.next = thirdNode
    thirdNode.next = nil

    // 測試刪除某個結點並遍歷打印刪除結點後的單鏈表
    linkedList := firstNode  // 鏈表頭節點指向 firstNode
    err := linkedList.delete(secondNode)
    if err != nil {
        fmt.Println(err)
    } else {
        linkedList.traverse()
        fmt.Println()
    }
}

執行測試代碼，打印結果如下，表明刪除成功：

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

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