LeetCode 面试题 02.02. 返回倒数第 k 个节点 【Kth Node From End of List LCCI】_python解决leetcod02.02返回链表倒数第k个节点本机测试

       互联网行业的小白，写博客的目的是为了记录自己的学习过程、对自己学习中所犯的错误做一个总结。由于水平有限，博客中难免会有一些错误出现，有纰漏之处恳请各位大佬不吝赐教！

题目描述

题目传送门：返回倒数第 k 个节点

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

示例：

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

说明：

给定的 k 保证是有效的。

题解

给出一个长度未知的链表，如何找到链表中倒数第n个结点? **最容易想到的当然是：**先从头到尾遍历链表，统计出链表的总长度，从而计算出倒数第n个结点相当于正数第几个结点。

比如链表总长度是10，倒数第3个结点就相当于正数第8个结点。然后从头遍历链表，遍历到第8个结点，就可得到结果。

AC代码

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

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        cur = head
        count = 0
        while cur is not None:
            count += 1
            cur = cur.next
        cur = head
        for i in range(1, count + 1):
            if i == count - k + 1:
                return cur.val
            cur = cur.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

但是这种方法需要经过两次遍历才能得到结果，如果只用一次遍历，是否可以得到结果？

当然是可以的啦

首先，我们创建两个指针p1和p2，p1指向链表的头结点，p2指向链表的正数第n个结点 。

接下来,我们让指针p1和p2同时循环右移，每次右移一步，直到指针p2移动到链表的末尾。

此时，由于p2指向链表的尾结点，且p1和p2的距离是n-1，因此p1所指的结点就是我们要寻找的链表倒数第n个结点。

显然，这个方法从头到尾只需要对链表做一次遍历，而且仅仅使用了两个指针，算法的空间复杂度是O(1)。

AC代码

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

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        p1 = head
        p2 = head
        # 把p2指针移动到正数第n个结点
        for i in range(k - 1):
            p2 = p2.next
        # p1和p2一起右移，直到p2指向链表尾结点
        while p2.next is not None:
            p1 = p1.next
            p2 = p2.next
        return p1.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

码字不易，您的支持就是我坚持下去的动力，一起加油哦。