链表中倒数第k个节点

【题目】：

输入一个链表，输出该链表中倒数第k个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

【解题思路】：

1. 使用双指针，一个先跑到第k个节点，然后第二个指针从头开始与第一个指针同时遍历，直到第一个指针指向空，此时第二个指针就指向倒数第k个节点；
2. 使用递归的回溯法【这儿未解答】。

示例代码1：

#  define a linklist
class LinkNode(object):def __init__(self, val):self.val = valself.next = None#  creat a linklist
def creat_linklist(li):if not li:returnhead = p = LinkNode(li[0])for i in li[1:]:p.next = LinkNode(i)p = p.nextreturn head#  find last k node
def find_last_node(head, k):if not head and k == 0:returnfirst, second = head, Nonefor i in range(k - 1):if first.next is not None:first = first.nextelse:return Nonesecond = headwhile first.next:first = first.nextsecond = second.nextprint(second.val)# test
head = creat_linklist([1, 2, 3, 4, 5, 6])
print("findKthToTail", end=": ")
find_last_node(head, 3)

运行结果：

示例代码2：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getKthFromEnd(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""p = q = headnum = 1while num != k and p:num += 1p = p.nextif num != k:return Nonewhile p.next:p = p.nextq = q.nextreturn q

示例代码3：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def getKthFromEnd(self, head, k):""":type head: ListNode:type k: int:rtype: ListNode"""res = []while head:res.append(head)head = head.nextreturn res[-k]