题目
剑指 Offer 22. 链表中倒数第k个节点
思路1（栈）
- 既然要倒数第k个节点，那我们直接把所有节点放到栈（先进后出）里面，然后pop弹出k个元素就可以了
代码
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
LinkedList<ListNode> stack = new LinkedList<>();
// 把整个链表入栈
while (head != null) {
stack.push(head);
head = head.next;
}
// 先将前n-1个元素出栈
for (int i = 1; i < k; i++) {
stack.pop();
}
// 此时位于栈顶的就是倒数第k个元素啦
return stack.pop();
}
}1
复杂度分析
- 时间复杂度：\(O(N)\)
- 空间复杂度：\(O(N)\)，使用栈的额外空间要花掉\(O(N)\)
思路2（递归+回溯）
- 和使用栈的思想差不多。。
- 先递归到链表末尾，然后依次回溯，回溯k次的时候就得到我们需要的节点了
代码
class Solution {
ListNode res;
// 代表当前处于倒数第几个节点
int cur = 0;
public ListNode getKthFromEnd(ListNode head, int k) {
dfs(head, k);
return res;
}
public void dfs(ListNode node, int k) {
// 先递归到末尾
if (node == null) {
return;
}
dfs(node.next, k);
// 倒数第cur个节点
cur++;
// 等于k代表找到了
if (cur == k) {
res = node;
}
}
}
复杂度分析
- 时间复杂度：\(O(N)\)
- 空间复杂度：\(O(N)\)，需要递归整个链表
思路3（双指针）
- 定义
fast快指针和slow慢指针两个指针：让快指针fast先走k步，然后再让两个指针同时移动，等快指针fast走道链表末尾时候（为null），此时慢指针slow所指向的节点就是倒数第k个节点
代码
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// 让快指针先走k步，和慢指针相差k个距离
for (int i = k; i > 0; i--) {
fast = fast.next;
}
// 此时让慢指针和快指针同时走，知道快指针到达链表末尾为null时，慢指针就在倒数第k个位置上了
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// 直接返回慢指针即为答案
return slow;
}
}
复杂度分析
- 时间复杂度：\(O(N)\)
- 空间复杂度：\(O(1)\)
思路4（差值法）
- 因为要求的是倒数第k个节点，那如果我们知道了链表的总长度，那么这个节点在链表中的顺序位置也就知道了
- 先计算出链表的总长度，则可以得出：
倒数第k个节点 等于 链表总长度-k+1。但是在题目中我们已经指向了链表的第一个节点，所以只需要再走n-k个节点即可到达倒数第k个节点
代码
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
int length = 0;
ListNode p = head;
// 先获取链表的总长度
while (p != null) {
p = p.next;
length++;
}
// 其实倒数第k个的位置就相当于 length-k
// 然后我们从链表头部开始遍历 length-k 个节点，此时所在的节点位置就是答案了
k = length - k;
for (int i = k; i > 0; i--) {
head = head.next;
}
return head;
}
}
复杂度分析
- 时间复杂度：\(O(N)\)
- 空间复杂度：\(O(1)\)