python链表 —— 找出单链表中的倒数第K个元素

题目描述：

找出单链表中的倒数第K个元素

算法描述

从头到尾遍历链表，在查找的过程中，设置两个指针，让其中的一个指针比另一个指针先向前移动K步，然后两个指针同时向前移动

代码实现第二种方法：

class LNode:
    def __init__(self, item):
        self.data = item
        self.next = None

#创建一个链表
def CreateLinkList():
    i= 1
    head = LNode(None)
    head.next = None
    tmp = None
    cur = head
    while i < 8:
        tmp = LNode(i)
        tmp.next = None
        cur.next = tmp
        cur = tmp
        i += 1
    return head

#打印链表
def PrintLinkList(head):
    cur = head.next
    while cur != None:
        print(cur.data, end=' ')
        cur = cur.next

#找出倒数第K个元素
def FindK(head, k):
    if head is None or head.next is None:
        return None
    slow = head.next
    fast = head.next
    #将fast向前移动K步
    i = 0
    while i < k and fast is not None:
        fast = fast.next #向前移动K步
        i += 1
    if i < k:
        return None
    while fast is not None:
        slow = slow.next
        fast = fast.next
    return slow

if __name__ == "__main__":
    head = CreateLinkList()
    result = None
    print("链表：")
    PrintLinkList(head)
    result = FindK(head, 3)
    if result is not None:
        print("\n链表的倒数第三个元素为%d"%result.data)

代码执行结果如下：

链表：
1 2 3 4 5 6 7 
链表的倒数第三个元素为5

 

算法性能分析：

这种方法只需要对链表进行一次遍历，时间复杂度是o(N),空间复杂度是o(1)