剑指offer 14. 链表中倒数第k个结点
链表中倒数第k个结点
http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a
14. 链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路
定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第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.
if head==None or k<=0:
return None
node1 = head
node2 = head
num = 0
while(node1.next!=None):
node1 = node1.next
if(num>=k-1):
node2 = node2.next
num+=1
if(num>=k-1):
return node2
return None
查看21道真题和解析
投递阿里云等公司10个岗位 >