面试题22：链表中倒数第k个节点

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

解题思路：这道题使用传统的两遍遍历指针可以得出结果，第一遍遍历得出链表的总节点数，然后根据计算，倒数第k个就是距离最后一个节点距离尾k-1，最后一个节点为整数第n个，所以倒数第k个节点位正数第n-(k-1)，即n-k+1个；第二次遍历找到该节点即可。但是这种节点需要遍历两遍链表，可以进一步提高效率。如下思维导图为只需要遍历一遍的思路：

这种思路的核心为运用两个指针，倒数第k个节点距离尾节点的距离是k-1，因此当begin节点到达尾节点时，behind节点到达倒数第k个节点

22.链表中倒数第k个节点.png

代码实现：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if k <=0 or head == None:  #特殊情况 直接返回
            return None
        begin = head
        behind = None
        for i in range(k-1):      #保证头指针和尾指针之间的间隔k-1
            if begin.next is None:
                return None
            else:
                begin = begin.next
        behind = head
        while(begin.next is not None): #behind指针到尾节点时，behind指针到倒数第k个节点
            begin = begin.next
            behind = behind.next
        return behind

提交结果：

牛客网提交结果

*** 举一反三：当一个指针遍历链表有困难时，可以考虑两个指针，一个快一个慢，完成题目要求，如当要找中间节点时，一个指针每次走两步，一个指针走一步，当快指针到尾节点后另一个指针到中间节点