剑指offer 14. 链表中倒数第k个结点

14. 链表中倒数第k个结点

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

思路
定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。

代码实现

# -*- 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 head==None or k<=0:
            return None
        node1 = head
        node2 = head
        num = 0
        while(node1.next!=None):
            node1 = node1.next
            if(num>=k-1):
                node2 = node2.next
            num+=1
        if(num>=k-1):
            return node2
        return None