第 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：推荐，设置快慢指针，快指针先走 步，然后快慢指针一起走。
C++ 代码：
image-20190108005842835
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;
}
}
