题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
准备两个指针，第一个指向头，让第二个先往后走k步，之后再同时走，当第二个指针到达尾部时第一个指针指向的刚好就是倒数第k个节点
Code
- Python
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
if head is None:
return None
p, q = head, head
while k > 1 and q.next is not None:
q = q.next
k -= 1
if k > 1 or k == 0:
return None
while q.next is not None:
p = p.next
q = q.next
return p
- JavaScript
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
if (!head) return null
let p = head, q = head
while(k-- > 1 && q.next) q = q.next
if (k) return null
while(q.next) {
p = p.next
q = q.next
}
return p
}
