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

执行测试代码，打印结果如下，表明删除成功：