题解 | #链表中倒数最后k个结点#
思路
使用栈暴力破解
-
用一个stack来存储push链表每个节点
-
然后循环k次pop出stack中的节点
时间复杂度 O(n) 空间复杂度 O(n)
计数法
-
先统计链表中元素的数目
-
再根据count-k的个数逆向求出需要遍历到的位置
-
然后直接返回头节点
时间复杂度 O(n) 空间复杂度 O(1)
快慢指针
-
先用fast快指针走k步
-
然后fast快指针和slow慢指针同时走，直到fast快指针为空，返回slow慢指针
时间复杂度 O(n) 空间复杂度 O(1)
//解法一 使用栈
if(!pHead) {
return null;
}
let stack = [];
while(pHead) {
stack.push(pHead);
pHead = pHead.next;
}
let target = null;
while (k && k <= stack.length) {
target = stack.pop();
k--;
}
return target;
//解法二 计数法
let count = 0;
let head = pHead;
let h = pHead;
while(h) {
count++;
h = h.next;
}
if (count<k) {
return null;
}
for(let i=0; i<count-k ; i++){
head = head.next;
}
return head
//解法三 快慢指针法
let slow = pHead;
let fast = pHead;
for(let i=0;i<k;i++){
if(!fast){
return fast;
}
fast = fast.next;
}
while(fast){
slow = slow.next;
fast = fast.next;
}
return slow;
美团公司氛围 2503人发布
