python算法-011找出单链表的倒数第k的元素

孤独的船只，扬起的帆，迷途的人，要去哪儿啊？我敬杯酒，妄想孤单，回家吧~
——林晨阳《船》

题目：给定一个单链表，找出其倒数第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->41-^  ^  ^  ^  ^  ^  ^  ^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 randomclass 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 Nonedef 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 Noneif __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。

孤独的人啊，不要悲伤，也许明天就看见了太阳。时光漫长，珍惜很短，别想了，跟我回家吧~
——林晨阳《船》