題目：

實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該鏈表中倒數第k個節點。

示例一：

輸入：{1,2,3,4,5},2

返回值：{4,5}

說明：返回倒數第2個節點4，系統會打印后面所有的節點來比較。

示例二：

輸入：{2},8

返回值：{}

思路如下：

用雙指針，可省去統計鏈表長度操作，算法流程為：

1. 初始化雙指針 pre , cur 都指向頭節點 head ；

2. 先令 cur 走 k 步，此時 pre , cur 的距離為 k ；

3. 令 pre , cur 一起走，直到 cur 走過尾節點時跳出，此時 pre 指向「倒數第 k 個節點」，返回之即可；

注意：

1.處理 k <= 0

if k <= 0 or not pHead:return None

2.檢查快指針移動時的越界

for _ in range(k):if not cur:  # 此時 cur 為 None，但循環尚未完成 k 次return Nonecur = cur.next

題解如下：

class Solution:def FindKthToTail(self , pHead, k):""":type:  pHead: ListNode, k: int:rtype: ListNode"""# write code hereif k <=0 or not pHead:return Nonepre, cur = pHead, pHeadfor _ in range(k):if not cur:return Nonecur = cur.nextwhile cur:pre, cur = pre.next, cur.nextreturn pre