剑指 Offer(六)

链表中倒数第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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 使用两个指针,a 先遍历 k-1,之后一起遍历,直到a 指针到最后一个节点,则 b 为倒数 k 节点
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def find_k_to_tail(self, head, k):
if not head and k <= 0:
return None
a_head = head
b_head = None
for i in range(k - 1):
if a_head.next != None:
a_head = a_head.next
else:
return None
b_head = head
while a_head.next != None:
a_head = a_head.next
b_head = b_head.next
return b_head.val
def find_k_to_tail2(self, head, k):
if not head and k <= 0:
return None
a_head = head
while a_head and (k - 1) >= 0:
a_head = a_head.next
k -= 1
while a_head:
a_head = a_head.next
head = head.next
return head.val
a = ListNode(1)
a.next = ListNode(2)
a.next.next = ListNode(3)
a.next.next.next = ListNode(4)
a.next.next.next.next = ListNode(5)
s = Solution()
print s.find_k_to_tail2(a, 3)