Press "Enter" to skip to content

Go 常见算法面试题篇(四):链表中倒数第 k 个结点

题目

前面几个题目考察的是考虑问题的全面性,接下来看几个考察代码健壮性的面试题。

所谓健壮性也叫鲁棒性(Robust),其核心要素是即使输入不符合要求的参数,也不至于让程序崩溃,也就是对各种异常和边界的处理。提高代码健壮性的有效方式是防御性编程,比如对参数的校验,对于不符合要求的参数予以返回或抛出异常处理。

下面我们来看今天的题目:

输入一个链表,输出该链表中倒数第 k 个结点。

为了符合大多数人的习惯,本题约定从 1 开始计数,即链表的尾结点是倒数第 1 个结点。例如一个链表有 6 个结点,从头结点开始它们的值依次是 1、2、3、4、5、6,那么这个链表的倒数第 3 个结点是值为 4 的结点。

解题思路

这个题目要分两种情况来看:

  • 如果是双向链表,就比较简单了,因为双向链表每个结点有两个指针,一个指向前驱结点,一个指向后驱结点,倒数第 k 个结点只需要从尾结点往前移动指针即可。
  • 如果是单向链表,就要复杂一些,因为没有前驱结点,我们需要先遍历一遍链表获取所有结点数 n,计算出倒数第 k 个结点的位置:n - k + 1,然后根据这个位置再次遍历链表,获取对应结点。

上述这种做法是没有问题的,但是遍历两次链表时间复杂度是 O(2n),我们可不可以对这个操作流程进行优化,通过 O(n) 即遍历一次链表就能获取到指定结点呢,大家可以先思考下。

答案是可以,这需要两个指针来实现,初始时两个指针都指向头结点,我们要保证两个指针的间距保持在 k-1,这样,当一个指针到达尾结点时,另一个指针刚好到达倒数第 k 个结点的位置。

为了实现这个目标,我们先让第一个指针往前走 k-1 步,第二个指针保持不动,接着从第 k 步开始,第二个指针也往前移动,这样一来两个指针就始终保持在 k-1 的距离,直到第一个指针到达尾结点,这个时候第二个指针指向的位置就是倒数第 k 个结点,并且整体下来的时间复杂度是第一个指针遍历了整个链表,时间复杂度是 O(n)。

有了以上思路代码实现起来就比较简单了,需要注意的是我们需要关注代码的鲁棒性,对输入参数要进行必要的校验,以免空指针异常。

实现代码

接下来,我们来编写对应的实现代码。

单链表结点类在 O(1) 时间内删除单链表结点这篇教程中已经定义过:

// Node 单链表结点类
type Node struct {
  data interface{}
  next *Node
}

时间复杂度为 O(2n) 的实现代码如下:

// 版本1:时间复杂度为 O(2n) 的实现
func findKthNodeToTailV1(head *Node, k int) (*Node, error) {
  // 参数无效
  if head == nil || head.next == nil || k <= 0 {
    return nil, errors.New("invalid params")
  }
​
  // 第一次遍历
  node := head
  n := 1
  for node.next != nil {
    n++
    node = node.next
  }
​
  // k 大于链表长度
  if k > n {
    return nil, errors.New("k is longer than linked_list length")
  }
​
  // k 和链表长度相等,则倒数第 k 个结点正好是头结点
  if k == n {
    return head, nil
  }
​
  // 其他情况需要从链表头部开始第二次遍历,拿到顺序第 n - k + 1 个结点返回
  target := n - k + 1
  n = 1
  node = head.next
  for node.next != nil {
    n++
    if  n == target {
      return node, nil
    }
    node = node.next
  }
​
  return nil, errors.New("node not found")
}

下面是时间复杂度为 O(n) 的实现代码:

// 版本2:时间复杂度为 O(n) 的实现
func findKthNodeToTailV2(head *Node, k int) (*Node, error) {
  // 参数无效
  if head == nil || head.next == nil || k <= 0 {
    return nil, errors.New("invalid params")
  }
​
  // 初始化两个指针
  aP := head
  bP := head
​
  // 只将 a 指针移动 k - 1
  for i := 0; i < k - 1; i++ {
    aP = aP.next
    // 到达链表尾结点,表明 k 大于链表长度
    if aP == nil {
      return nil, errors.New("k is longer than linked_list length")
    }
  }
​
  // 同时移动 a、b 指针,直到 a 到达链表尾结点
  for aP.next != nil {
    aP = aP.next
    bP = bP.next
  }
​
  // 返回 b 指针对应的结点,就是链表倒数第 k 个结点
  return bP, nil
}

最后编写链表初始化和测试代码如下:

func main() {
  // 初始化单链表
  head := &Node{
    data: 1,
  }  // 头结点
  prev := head    // 记录上一个结点
  for i := 2; i <= 6; i++ {
    node := &Node{
      data: i,
    }
    prev.next = node
    prev = node
  }
​
  // 测试代码
  // v1
  k := 3
  h1 := head
  kNodeV1, err := findKthNodeToTailV1(h1, k)
  if err != nil {
    fmt.Println(err)
    return
  }
  fmt.Printf("单链表倒数第 %d 个结点v1: %#v\n", k, kNodeV1)
​
  // v2
  h2 := head
  kNodeV2, err := findKthNodeToTailV1(h2, k)
  if err != nil {
    fmt.Println(err)
    return
  }
  fmt.Printf("单链表倒数第 %d 个结点v2: %#v\n", k, kNodeV2)
}

执行代码,打印结果如下,表示代码测试通过:

image-20211123213226394

太烂了有点差凑活看还不错太棒了 (1 人打了分, 平均分: 5.00)
Loading...
发表评论