题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
假设链表中的节点数大于等于k个，那么一定会存在倒数第k个节点，首先使用一个快指针先往前走k步，然后两个指针每次走一步，两个指针之间始终有k的距离，当快指针走到末尾时，慢指针所在的位置就是倒数第k个节点。
做题可能出现的问题
考虑k小于0的情况，其次就是链表的长度是否够k个长度
python
# -*- 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 not head or k<=0:
return None
p = q = head
count = 0
while q is not None and count<k:
q = q.next
count += 1
if count<k:
return None
while q is not None:
q = q.next
p = p.next
return p
C++
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode *ptr1 = pListHead; // 指针１
ListNode *ptr2 = pListHead; //指针２
if (pListHead == NULL || k == 0)//考虑全面
return NULL;
int i;
for(i=0;i<k-1;i++) // p1 走k-1步
{
if(ptr1->next) // 这个条件等价于方法一种的，if(n<k)return NULL; 因为当i<k-1时,如果发生ptr1->next==null，说明k太大了，超出了链表的总结点个数
ptr1 = ptr1->next;
else
return NULL;
}
while(ptr1->next) // p1走到end， p2开始走
{
ptr1=ptr1->next;
ptr2=ptr2->next;
}
return ptr2;
}
};
