searchusermenu
  • 发布文章
  • 消息中心
点赞
收藏
评论
分享
原创

链表中倒数第k个结点-算法学习

2023-07-11 10:13:25
1
0

题目详情:
输入一个链表,输出该链表中倒数第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");
}

0条评论
作者已关闭评论
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
t****m
98文章数
1粉丝数
t****m
98 文章 | 1 粉丝
原创

链表中倒数第k个结点-算法学习

2023-07-11 10:13:25
1
0

题目详情:
输入一个链表,输出该链表中倒数第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");
}

文章来自个人专栏
js
57 文章 | 1 订阅
0条评论
作者已关闭评论
作者已关闭评论
0
0