1. 解题思路
一般链表题，我们都可以考虑双指针的解题思路，此题同样可以。首先注意题目描述里这句👇
“如果该链表长度小于k，请返回一个长度为 0 的链表。” 意味着如果链表为空，那么直接返回None即可。
然后结合示例1，继续分析：
- 首先创建两个指针，指向头部节点：
- 然后根据k值，移动first指针走k步，所以示例会进行如下移动：
- 接着first走完k步后，first和second开始同步指针移动：
最后直到first到null位置，此时second的位置就是本题要求的。
2. 核心代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
def FindKthToTail(self , pHead , k ):
# write code here
#首先初始化两个指针，都指向头节点
first, second = pHead, pHead
#当first不存在的时候，直接返回None
for i in range(k):
if first == None:
return None
#否则节点存在，开始移动first指针走动k步
first = first.next
#当first走完k步后，此时first、second指针开始同步移动，当first移出链表到null的位置，second指针停止移动;此时返回second指针所在位置就是我们要找的倒数最后K个节点值
while first:
first = first.next
second = second.next
return second 3. 复杂度分析
- 时间复杂度：
(n 为链表的长度，first走了n步，second走了(n - k)步)
- 空间复杂度：
(双指针使用常数大小的额外空间)
-------------------------------------------我是解法二的分割线---------------------------------------------------
4. 解法二
4.1 思路
利用数组的切片规则直接获取倒数的k个节点。（就是这么简单😂）
4.2 核心代码
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
def FindKthToTail(self , pHead , k ):
# write code here
#创建一个空数组
list = []
#当节点存在时，依次添加节点到数组中
while pHead:
list.append(pHead)
pHead = pHead.next
#根据题目描述，当k大于数组长度的时候或k为0 的时候，返回None
if k > len(list) or k == 0:
return None
else: #否则根据切片规则返回倒数K个节点
return list[-k]4.3 复杂度分析
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号