方法一:两次遍历
第一次遍历,计算链表的长度
第二次链表,到达倒数第 $k$ 个节点即是答案
时空复杂度
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
Java 代码
class Solution {
public ListNode findKthToTail(ListNode pListHead, int k) {
if (pListHead == null || k == 0) {
return null;
}
// 计算链表节点数 size
ListNode cur = pListHead;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
// 如果 k > size,那么倒数第 k 个节点不存在
if (k > size) {
return null;
}
cur = pListHead;
for (int i = 0; i < size - k; i++) {
cur = cur.next;
}
return cur;
}
}
方法二:双指针一次遍历
定义双指针 former
、latter
,两个指针都从头节点出发
让 former
先走 $k$ 步,之后两个指针一起走
当 former
遍历结束时,latter
指向的节点就是答案
时空复杂度
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
Java 代码
class Solution {
public ListNode findKthToTail(ListNode pListHead, int k) {
if (pListHead == null || k == 0) {
return null;
}
// 双指针
ListNode former = pListHead, latter = pListHead;
// 前指针先走k步
for (int i = 0; i < k; i++) {
if (former == null) {
return null;
}
former = former.next;
}
// 两个指针一起走
while (former != null) {
former = former.next;
latter = latter.next;
}
return latter;
}
}