剑指offer：链表中倒数第k个结点 Python |考虑未知量的取值情况的return

#coding:utf-8
###1 链表
##1.2 题15 链表中倒数第k个结点
##题目：输入一个链表，输出该链表中导数第k个结点

#关于链表：
# class ListNode:
#     def __init__(self, x):
#         self.val = x # val表示value
#         self.next = Node # next表示指针

#方法一:计算链表长度，计算需要的循环次数，for循环。
class Solution:
    def FindKthToTail(self, head, k):
        len_node = 0
        temp = head #临时设定一个指针
        #假设我们有一个长度为3的链表，现在用循环输出他的长度
        #从第一个结点开始循环：判断temp不为None，则开始第一次循环，temp指向第二个结点，长度记为1
        #判断temp不为None（指向第二个结点），开始第二次循环，temp指向第三个结点，长度记为2
        #判断temp不为None（指向第三个结点），开始第三次循环，此时temp=None，长度记为3
        #判断temp为None,循环结束，此时得出长度为3
        while temp:
            temp = temp.next #指向下一个结点
            len_node += 1
        #假设链表长度为10，求倒数第3个位置的结点，那么这个结点应该在第8个的位置
        #run_times = 7
        run_times = len_node - k
        if run_times < 0 or k < 0 :
            return
        for i in range(run_times):
            #循环7次，指针指向第8个位置，即为倒数第3
            head = head.next
        return head

#方法二：计算链表长度，设置两个不同的指针，第一个指针在第K个位置，第二个指针在第1个位置，
#两个指针同时next，当第一个指针到达尾部时，第二个指针的位置即为倒数第k个
class Solution:
    def FindKthToTail(self, head, k):
        len_node = 0
        temp = head
        while temp:
            temp = temp.next
            len_node +=1
        if len_node < k or k < 0:
            return
        quick_listnode = head
        slow_listnode = head
        for i in range(k):
            quick_listnode = quick_listnode.next
        while quick_listnode:
            quick_listnode = quick_listnode.next
            slow_listnode = slow_listnode.next
        return slow_listnode