题目详情:
输入一个链表,输出该链表中倒数第k个结点。
示例:
输入:1,{1,2,3,4,5}
输出:{5}
解题思路:
首先定义链表的数据结构,可以使用对象表示节点,包含一个值和下一个节点的引用。
创建一个函数 findKthFromEnd,接收一个链表头节点和整数 k 作为参数。在函数内部,使用双指针法来查找倒数第 k 个节点。
代码实现:
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function findKthFromEnd(head, k) {
let slow = head;
let fast = head;
// 快指针先移动 k 步
for (let i = 0; i < k; i++) {
if (fast === null) {
return null; // 如果链表长度小于 k,返回 null
}
fast = fast.next;
}
// 快慢指针一起移动,直到快指针到达链表尾部
while (fast !== null) {
slow = slow.next;
fast = fast.next;
}
return slow; // 返回倒数第 k 个节点
}
// 构造链表:1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
const k = 3; // 倒数第 k 个节点的位置
const result = findKthFromEnd(head, k); // 输出 3
// 输出倒数第 k 个节点
if (result !== null) {
console.log(result.val);
} else {
console.log("链表长度小于 k");
}