返回倒数第 k 个节点

返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

示例代码1：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def kthToLast(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: int
        """
        a, b = head, head
        for _ in range(k):
            b = b.next
        while b:
            a = a.next
            b = b.next
        return a.val


        

示例代码2：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def kthToLast(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: int
        """
        if not head:
            return None
        data = []
        while head:
            data.append(head.val)
            head = head.next
        return data[-k]


        

解题思路：

方法一：     在不知道链表长度的情况下，需要知道倒数第k个节点可以借助一个临时节点p,让他先走k步。     然后head和p一起往后移，当p走到末尾的时候，head指向的节点就是我们要求的节点。

方法二：     遍历链表，将value存入一个数组