剑指offer 面试题22. 链表中倒数第k个节点（易）

使用快慢指针解题即可，关键是写出更加鲁棒的代码。

Question

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

测试用例

功能测试（第k个节点在链表的中间；第k个节点是链表的头节点；第k个节点是链表的尾节点）。 特殊输入测试（链表头节点为 nullptr 指针；链表的节点总数少于k；k等于0）。

考点

考查应聘者对链表的理解。 考查应聘者所写代码的鲁棒性。鲁棒性是解决这道题的关键所在。如果应聘者写出的代码有着多处崩溃的潜在风险，那么他是很难通过这轮面试的。

Intuition

有不少人在面试之前从网上看到过用两个指针遍历的思路来解这道题，因此听到面试官问这道题，他们心中一阵窃喜，很快就能写出代码。 可是几天之后他们等来的不是Offer，而是拒信，于是百思不得其解。其实原因很简单，就是自己写的代码不够鲁棒。面试官可以找出3种办法让这段代码崩溃。

  1. 输入的pListHead为空指针（空链表）。由于代码会试图访问空指针指向的内存，从而造成程序崩溃
  2. 输入的以pListHead为头节点的链表的节点总数少于k。由于在快指针会在链表上向前走k步，最终会报错越出原链表。
  3. 输入的参数k为0，按理应该输出 None，也确实是输出了 None，原来书中的那种写法会出问题，Python3写不会报错。

Code

  • 原代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast = head
        slow = head
        while k:
            fast = fast.next
            k -= 1
        while fast:
            fast = fast.next
            slow = slow.next
        return slow
  • 更加鲁棒的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        if not head:  return None  # 空链表自动就会返回None
        fast = head
        slow = head
        # 如果输入的k=0，那么fast和slow会一起一直循环访问到最后一个节点的next指针所指向的None，会返回None
        while k:
            fast = fast.next
            k -= 1
            if k > 0 and fast == None:  # 说明输出的k大于链表长度 直接返回None
                return None
        while fast:
            fast = fast.next
            slow = slow.next
        return slow