1.链表中的第k个节点
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
注意:该题目曾经在美团的笔试算法题中出现。
示例:
1.哈希表实现
这里我们可以采用哈希表求解该问题:
首先遍历链表,将链表中的节点以键值对的形式存储在哈希表中,哈希表的键为节点的位置(从1开始),值为当前节点,由于倒数第k个节点正好是正数第n-k+1个(n为链表的长度),所以就是哈希表中索引为n-k的value,将其从哈希表中取出并返回即可。
具体代码如下所示:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
Map<Integer,ListNode> hash=new HashMap<>();
ListNode p=head;
int num=1;
while(p!=null){
hash.put(num,p);
p=p.next;
num++;
}
p=hash.get(num-k);
return p;
}
}
2.时间复杂度分析
由于时间上是对链表的一次遍历,所以时间复杂度为 O ( n ) O(n) O(n),这里空间上使用了哈希表存储对应的链表位置与链表节点,所以空间复杂度也为 O ( n ) O(n) O(n),具体代码在LeetCode中的执行情况如下所示:
3.顺序查找
有前面的分析得知,倒数第k个元素节点就是正数第n-k+1个节点,所以问题的关键就在先求出链表节点的总数n,在将指针指向第n-k+1个链表节点并返回即可求解该问题,具体代码如下所示:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
int n=0;
ListNode p=null;
//确定链表的长度
for(p=head;p!=null;p=p.next){
n++;
}
p=head;
for(int i=0;i<n-k;i++){
p=p.next;
}
return p;
}
}
注意:查找第n-k+1个链表节点时,由于p又重新指向head头结点,为第一个元素,所以只需要移动n-k此即可指向链表第n-k+1个节点。
4.时间复杂度分析
由于本次算法实现时间上仍然是链表的遍历,第一次遍历是确定链表的长度,第二次遍历是查找第n-k+1个链表节点。所以时间复杂度仍是 O ( n ) O(n) O(n),而本次算法实现并未采用哈希表存储节点,因此空间复杂度为 O ( 1 ) O(1) O(1),具体算法在LeetCode中的执行情况如下所示:
5.快慢指针实现
快慢指针的思想。我们将第一个指针 \textit{fast}fast 指向链表的第 k + 1个节点,第二个指针 slow \textit{slow} slow 指向链表的第一个节点,此时指针 fast \textit{fast} fast 与 slow \textit{slow} slow二者之间刚好间隔 k k k个节点。此时两个指针同步向后走,当第一个指针 fast \textit{fast} fast走到链表的尾部空节点时,则此时 slow \textit{slow} slow指针刚好指向链表的倒数第 k k k个节点。
我们首先将 fast \textit{fast} fast指向链表的头节点,然后向后走 k k k步,则此时 fast \textit{fast} fast指针刚好指向链表的第 k + 1 k + 1 k+1个节点。
我们首先将 slow \textit{slow} slow指向链表的头节点,同时 slow \textit{slow} slow与 fast \textit{fast} fast同步向后走,当 fast \textit{fast} fast指针指向链表的尾部空节点时,则此时返回 slow \textit{slow} slow所指向的节点即可。
具体的代码如下所示:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast=head;
ListNode slow=head;
//将fast指针向前移动k位
while(fast!=null && k>0){
fast=fast.next;
k--;
}
//将快慢指针同时向后移动
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
6.GIF动图展示
这里以链表{1,2,3,4,5}为例,查找倒数第2个元素的GIF动图
本次算法的实现,这里仍然只是对链表的遍历,因此时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1)。具体代码在LeetCode中的执行情况如下所示: