链表的倒数第K个节点(简单) yinshibanxian

一、题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

示例

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

二、题目解析

1. 遍历法

   遍历整个链表，得到链表的长度length，则倒数第k个节点就是链表的第length - k + 1个节点，

   也就是从头节点走length - k步到达的节点。

    /**
    * 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 length = 0;
        let current = head;
        while(current != null) {
            length ++;
            current = current.next;
        }
        let index = length - k + 1;
        current = head;
        while(index > 1) {
            index --;
            current = current.next;
        }
        return current;
    };
   

   • 时间复杂度: O(n)，n为链表的长度
   • 空间复杂度: O(1)

2. 双指针法

   双指针法不需要得到链表的长度，只需要构建former,latter两个指针，具体步骤如下：

   • 定义former,latter两个指针，former指针先向前走k步，此时former和latter相距k步
   • former和latter同时向前走，直到former指向链表的最后一个元素，此时latter即指向了倒数第k个链表元素
   • 返回latter指针即可

    /**
    * 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 former = head,latter = head;
        for(let i = 0;i < k;i ++) {
            former = former.next;
        }
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    };
   

   • 时间复杂度: O(n),n为链表长度
   • 空间复杂度： O(1)

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof