<a href="https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/sub

思路 [其实有两种解法。一种<a href="https://github.com/liuqh0609/algorithm/issu

相对暴力的解法： <div class="highlight highlight-source-js notranslate position-relative o

22. 链表中倒数第k个节点 about algorithm HOT 4 OPEN

callqh commented on June 7, 2024

22. 链表中倒数第k个节点

from algorithm.

Comments (4)

callqh commented on June 7, 2024

思路

[其实有两种解法。一种相对暴力的解法就是对链表进行两次遍历，一次找出链表的总长度，另一次就是找到n-k个节点就是倒数第k个节点。
而我们这里采用一种一遍遍历就可以解决的方法。

定义两个指针都指向链表的起始节点
先让一个指针p2，提前走k步
这时另一个指针p1与p2，之间相差的距离就是k，然后让两个指针同时移动
当p2===null时，说明链表结束，那么这时p1指向的就是倒数第k个节点

from algorithm.

callqh commented on June 7, 2024

相对暴力的解法：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let p = head,p1=head;
    let count = 0;
    while(p!==null){
        count++;
        p = p.next;
    }
    for(let i = 0; i < count-k; i++){
        p1=p1.next;
    }
    return p1;
};