题目描述
输入一个链表，输出该链表中倒数第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
#最笨的方法，先找到最后一个节点，计算节点个数，找到倒数第k个节点的正数位置
p = head
i = 0
while p:
i += 1
p = p.next
#返回len-k个位置的节点（从0开始计数时）
j = 1
if i<k:
return None
while j<=i-k:
j += 1
head = head.next
return head
'''
#使用两个指针，相隔k步
left = right = head
for i in range(k):
if right==None:
return None
right = right.next
while right:
right = right.next
left = left.next
return left
'''
思路
两种思路，一种比较笨的方法，一种相对巧得办法。
第一种：通过第一次遍历整个链表，得到所有节点得个数，比如有5个结点，1->2->3->4->5,返回倒数第二个结点，就是4，他所在的正数位置是第（5-2=3）个位置（从0开始计数）。在第二次遍历的时候在遍历到第3个位置就停止，直接输出即可。
第二种：通过设置两个指针分别指向两个位置序号相差k的节点，其实中间相隔k-1个节点。然后二者同步向后移动，直到最右侧的指针所指节点移到尾节点的下一节点，即所指为空时，左侧指针所指即为倒数第k个节点。
