孤独的船只，扬起的帆，迷途的人，要去哪儿啊？我敬杯酒，妄想孤单，回家吧~
——林晨阳《船》
题目：给定一个单链表，找出其倒数第k个元素。例如：head->1->3->4->6->7->0->2->4->5->8->3->1,k=3,则倒数第三个元素为8。
今天的题目相比昨天的很简单，但是也有一定的技巧。先来分析下题目：给定的是单链表，只能从头向后遍历，因此他要查倒数第k个，也还是要从头开始查。要求是倒数第k个，那么如何判断当前的节点是否是倒数第k个，就是我们必须要解决的问题。一般我们先想到的是：先遍历一次链表，算出链表的长度N，那么我们求倒数第k个的问题，就可以转换为——求正序第N-k+1个元素。这个算法实现很简单，但是时间复杂度为O(N^2)，这不是我们希望看到的。后面我会介绍一种快的方法，先来看一下这个——"转换问题法"如何用代码实现：
#函数开始
#输入链表头以及k值
def FindLastButK_1(head,k):
#如果链表非空则执行
if head.next is not None:
cur=head #因为这里是计算链表长度，需要将第一个节点也算上
i=0 #用于记录链表长度
while cur.next is not None:
i+=1
cur=cur.next
#将问题转化为求 正序数第n-k+1个元素
n=i-k+1
#遍历到正序第N-k+1个元素
cur=head
while n>0:
cur=cur.next
n=n-1
#返回要求的元素
return cur.data
return None
这算代码非常简单，没有什么难度，加上这么详细的注释，我的室友都能看懂了。
下面来看一下一个比较新奇的方法，在学习之前我反正没想到：
用两个指针——slow和fast，从名字上看就是——快慢指针法。那么如何一个快慢指针呢？接着看->
在开始遍历时fast比slow快k-1步，比如k=3,那么
slow=head.next
fast=slow.next.next
然后slow与fast一起向前遍历，每次一个节点，直到fast到达最后一个节点。此时的slow刚好到达倒数第K个元素。
看下面的字符图：
K=3
1->3->4->6->7->0->2->4
1-^ ^ ^ ^ ^ ^ ^ ^
2-| | | | | | | |
3-s | | f | | | |
4- s | | f | | |
5- s | | f | |
6- s | f |
7- s f
这样是不是很好理解。只需要在开头处理下slow和fast，就可以实现找到倒数第k个元素。下面我们来用代码实现这里本来想给两个版本，一个用循环处理，一个用exec语句，但是exec我不会用，一用就错：
#用循环处理的
def FindLastButK_2(head,k):
i=0
slow=head.next
fast=head.next
#这里用一个循环来处理fast
while k-1>0:
fast=fast.next
k-=1
#我本来想用exec语句完成的但是我不会，怎么写都不对，很难受
#以后有空我会加上的
#判断链表是否为空，不空开始遍历，每次一步
if head.next is not None:
while fast.next is not None:
slow=slow.next
fast=fast.next
#当fast到达最后一个节点时，slow刚好是倒数第K个
return slow.data
return None
下面来看下程序运行：
if __name__ == '__main__':
head=creatLink(10)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
k=int(input("请输入k:\n"))
item1=FindLastButK_1(head,k)
item2=FindLastButK_2(head,k)
print("FindLastButK_1\n链表倒数第k个元素为：",item1)
print("FindLastButK_2\n链表倒数第k个元素为：",item2)
运行结果：
3
5
10
我把两种方法都运行了。
全部代码：
import random
class LNode:
def __init__(self,arg):
self.data=arg
self.next=None
"""
题目描述：
给定链表Head->1->1->3->3->5->7->7->8
单链表倒数第k=3个元素为7
要求：
方法：遍历链表计算链表长度n,然后求顺序第n-k+1个元素即可，再遍历一遍链表就可以得到结果
"""
#先构造链表
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(1, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
#函数开始
#输入链表头以及k值
def FindLastButK_1(head,k):
#如果链表非空则执行
if head.next is not None:
cur=head #因为这里是计算链表长度，需要将第一个节点也算上
i=0 #用于记录链表长度
while cur.next is not None:
i+=1
cur=cur.next
#将问题转化为求 正序数第n-k+1个元素
n=i-k+1
cur=head
while n>0:
cur=cur.next
n=n-1
return cur.data
return None
def FindLastButK_2(head,k):
i=0
slow=head.next
fast=head.next
while k-1>0:
fast=fast.next
k-=1
#exec('''"fast=head.next"+".next"*(k-1)''')
if head.next is not None:
while fast.next is not None:
#print("s",slow.data)
#print("f",fast.data)
slow=slow.next
fast=fast.next
return slow.data
return None
if __name__ == '__main__':
head=creatLink(10)
print("head:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
k=int(input("请输入k:\n"))
item1=FindLastButK_1(head,k)
item2=FindLastButK_2(head,k)
print("FindLastButK_1\n链表倒数第k个元素为：",item1)
print("FindLastButK_2\n链表倒数第k个元素为：",item2)
今天的算法就到这里，明天写爬虫。
下午学习的时候，遇到了一个。。。不算bug的bug，是我自己学的不扎实。我想在函数中更改全局变量的值，但是并没有告诉函数，那是个全局变量。电脑就把他当成局部变量了，不巧的是我还递归的调用了该函数，于是就出现了各种问题，我想了各种办法——把函数写成类的一个方法，把全局变量作为类的固有属性、把全局变量便成局部变量·····总之我是越来越烦，然后越来越错，错的更离谱！！！
我睡了一觉，醒过来我在最初的函数第一行加了一句global x.........解决了。
大家有什么需要都可以来找我，简书号、微信公众号：Dkider 私信、简信，都可以找到我。
更多的问题以及文章源码见github。
孤独的人啊，不要悲伤，也许明天就看见了太阳。时光漫长，珍惜很短，别想了，跟我回家吧~
——林晨阳《船》
网友评论