[剑指 Offer 第 2 版第 22 题] “链表中倒数第k个结点”做题记录.md

第 22 题：输入一个链表，输出该链表中倒数第 k 个结点

传送门：AcWing：链表中倒数第 k 个节点，牛客网 online judge 地址。

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

注意：

• k >= 0;
• 如果 k 大于链表长度，则返回 NULL;

样例：

输入：链表：1->2->3->4->5，k=2

输出：4

分析：设置快慢指针，思路很简单，不过在具体编码的时候，还是有一些细节要注意的，特别是空指针的判断上。

• 因为第 k 个结点很可能是链表的第 1 个结点，因此设置虚拟头结点，是这一列问题的基本做法，可以减少分类讨论的情况。
• 对一些极端情况的讨论（下面代码中的注意点 2 ）。

思路1：先遍历完，数出链表有多少个结点。

Python 代码：

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def findKthToTail(self, pListHead, k):
            """
            :type pListHead: ListNode
            :type k: int
            :rtype: ListNode
            """
            if pListHead is None:
                return None
            counter = 0
            p = pListHead
            while p:
                counter += 1
                p = p.next
            if k > counter:
                return None
            p = pListHead
            for _ in range(counter - k):
                p = p.next
            return p

思路2：推荐，设置快慢指针，快指针先走 k-1 步，然后快慢指针一起走。

C++ 代码：

Python 代码：

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    class Solution(object):
        def findKthToTail(self, pListHead, k):
            """
            :type pListHead: ListNode
            :type k: int
            :rtype: ListNode
            """
            if pListHead is None:
                return None
            fast = pListHead
            # 要注意的临界点1：
            for _ in range(k - 1):
                fast = fast.next
                # 注意判断
                if fast is None:
                    return None
            slow = pListHead
            # 要注意的临界点2：
            while fast.next:
                slow = slow.next
                fast = fast.next
            return slow

Java 代码：

  class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        public ListNode FindKthToTail(ListNode head, int k) {
            // 注意点1：极端输入，直接输出结果
            if (head == null) {
                return null;
            }
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            ListNode fast = dummyNode;
            for (int i = 0; i < k; i++) {
                fast = fast.next;
                // 注意点2：对不符合要求的输入的判断
                if (fast == null) {
                    return null;
                }
            }
            ListNode slow = dummyNode;
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/