剑指 Offer 22. 链表中倒数第k个节点【快慢指针】

题目描述

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

1
2
3
给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解题思路

方法:双指针[快慢指针]

双指针,使用快慢指针进行,快指针post先走K步后,慢指针cur同快指针post一同向前走,直到快指针走到尽头,此时慢指针就是倒数第K个指针。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
// 假设此方法 k 是有效的,解决本题足以。
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode post = head, cur = head;
for (int i = 0; i < k; i++) {
post = post.next;
}
while (post != null) {
cur = cur.next;
post = post.next;
}
return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 假设此方法 k 是任意数
// 先计算链表长度,判断k是否有效
public ListNode getKthFromEnd2(ListNode head, int k) {
if (k < 1) { //本题从1开始
return null;
}
int len = 0;
ListNode dummyHead = head;
while (dummyHead != null) {//计算链表的长度
len++;
dummyHead = dummyHead.next;
}
if (k < 1 || k > len) { //k超出1~len的范围为无效范围
return null;
}
ListNode post = head, cur = head;
for (int i = 0; i < k; i++) {
post = post.next;
}
while (post != null) {
cur = cur.next;
post = post.next;
}
return cur;
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

资源

  1. https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
  2. 《剑指offer》

剑指 Offer 22. 链表中倒数第k个节点【快慢指针】

http://example.com/2021/04/19/22-链表中倒数第k个节点/

Author

John Doe

Posted on

2021-04-19

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.