0%

剑指offer-22链表中倒数第K个结点-python

《剑指offer》python实现系列,全目录

第一想法:

走两遍,第一次统计链表中结点的个数,第二次找到第n-k+1个结点

要求只遍历一次怎么做?

两个指针,保持k-1的距离。第一个指针先向前走k-1个结点,第二个指针再走。当第一个指针到达尾结点的时候,第二个指针指向倒数第K个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def FindKthToTail(self, head, k):
if head is None or k<=0:
return
firstPos = head
secondPos = head
length = 1
firstKFlag = False #firstpos已经先走了k-1的标志
while firstPos.next is not None:
# K取值合理
if firstKFlag == False:
for _ in range(k-1):#firstPos先走k-1个结点
if firstPos.next is not None:
firstPos = firstPos.next
length += 1
else:#k大了
return
firstKFlag = True
continue
firstPos = firstPos.next
secondPos = secondPos.next
length += 1
if length < k:
return
return secondPos
if help:小手一抖点个广告 or 大手一挥资助一下