链表中倒数第k个节点

 链表中倒数第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 = val
        self.next = None


#  creat a linklist
def creat_linklist(li):
    if not li:
        return
    head = p = LinkNode(li[0])

    for i in li[1:]:
        p.next = LinkNode(i)
        p = p.next
    return head


#  find last k node
def find_last_node(head, k):
    if not head and k == 0:
        return

    first, second = head, None
    for i in range(k - 1):
        if first.next is not None:
            first = first.next
        else:
            return None
    second = head
    while first.next:
        first = first.next
        second = second.next
    print(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 = None

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        p = q = head
        num = 1
        while num != k and p:
            num += 1
            p = p.next
        if num != k:
            return None
        while p.next:
            p = p.next
            q = q.next
        return q

示例代码3：

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

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        res = []
        while head:
            res.append(head)
            head = head.next
        return res[-k]