面试题22：链表中倒数第k个节点

# -*- coding:utf-8 -*-

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def FindKthToTail(self, head, k):

        # write code here

        # 先考虑k若大于链表的长度，返回None,链表的长度咋算，不太会,可以在遍历的时候count+1

        # 我的思路是，从头到尾遍历链表，将其存在list中，如果len(list)<k,返回None；如果k=0，也返回None

        result = []

        while head:

            result.append(head)

            head = head.next

        if k > len(result) or k == 0:

            return None

        return result[len(result)-k]

　思路2：参考书书中的解题思路，只遍历一遍链表，就可以找到倒数第k个节点。我们这样思考，倒数第k个就是正数第n-k+1个。可以设置2个指针，2个指针相差k-1步，当前面的走的指针走到最后了，那我们的后指针就走到了n-k+1的位置。

# -*- coding:utf-8 -*-

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def FindKthToTail(self, head, k):

        # write code here

        if head == None:

            return None

        pointer1 = head

        pointer2 = head

        count = 0

        while pointer1:

            if count > k-1:

                pointer2 = pointer2.next

            count += 1

            pointer1 = pointer1.next

        if count<k or k<=0:

            return None

        return pointer2