链表中倒数第k个结点

题目描述
输入一个链表，输出该链表中倒数第k个结点。
方法一：先计数，在查询，相当于遍历两遍。

def FindKthToTail(self, head, k):
    # write code here
    if not head:
        return None
    node = head
    count = 0
    while node:
        node = node.next
        count += 1
    if k > count:
        return None
    while count - k:
        head = head.next
        k += 1
    return head

方法二：将所有值存到一个list里，只遍历一遍。

def FindKthToTail(self, head, k):
    # write code here
    l=[]
    while head!=None:
        l.append(head)
        head=head.next
    if k>len(l) or k<1:
        return
    return l[-k]

方法三：两个指针都指向头结点，一个指针先走k-1个节点，然后两个指针一起走，直到一个指针到达尾部。时间复杂度O(n),一次遍历。

def FindKthToTail(self, head, k):
    # write code here
    if not head:
        return None
    p = head
    q = head
    count = 0
    while p:
        p = p.next
        count += 1
        if count >= k+1:
            q = q.next
    if k > count:
        return None
    return q