题目描述
输入一个链表，输出该链表中倒数第k个结点。
解析
设置两个指针，一个遍历链表到第k-1个结点，第二个再开始遍历，直到遍历到链表的最后一个结点，那么第二个指针指向的，就是倒数第k个结点。
Java
/**
* 运行时间：25ms
* 占用内存：9628k
*/
public ListNode FindKthToTail(ListNode head, int k) {
if (k <= 0)
return null;
ListNode p = head;
for (int i = 0; i < k; i++) {
if (head == null)
return null;
head = head.next;
}
while (head != null) {
p = p.next;
head = head.next;
}
return p;
}
/**
* 运行时间：23ms
* 占用内存：9444k
*/
public ListNode FindKthToTail2(ListNode head, int k) {
ListNode p, q;
p = q = head;
int i = 0;
for (; p != null; i++) {
if (i >= k)
q = q.next;
p = p.next;
}
return i < k ? null : q;
}
Python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class FindKthToTail:
# 运行时间：26ms
# 占用内存：6376k
def findKthToTail(self, head, k):
if head == None or k <= 0:
return None
p2 = head
p1 = head
while k > 1:
if p2.next != None:
p2 = p2.next
k -= 1
else:
return None
while p2.next != None:
p1 = p1.next
p2 = p2.next
return p1
