单向链表求最后第k个节点 给定一个单链表(每个节点都连向其后边的节点,但没有反向边)求离末尾点距离为k的节点。要求只允许一次遍历。js
时间: 2024-10-23 18:12:28 浏览: 13
你可以使用双指针法来解决这个问题。以下是JavaScript的实现方法:
```javascript
function findKthToTail(head, k) {
let slow = head;
let fast = head;
// 如果链表为空或k小于等于0,返回null
if (!head || k <= 0) {
return null;
}
// 快慢指针,快指针先前进k步
while (fast && k > 0) {
fast = fast.next;
k--;
}
// 如果k还没到头,说明找不到k步后的节点,返回null
if (fast === null) {
return null;
}
// 同时移动两者直到快指针到达尾部
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
// 返回slow节点,它就是倒数第k个节点
return slow;
}
```
这段代码首先初始化两个指针`slow`和`fast`,然后让`fast`指针向前移动k步。如果`k`大于0并且`fast`未达到链表尾部,那么`k`步之后不存在节点,所以返回`null`。当`fast`到达链表尾部时,`slow`指针的位置就是倒数第k个节点。这个方法保证了一次遍历即可找到答案。
阅读全文