链表中倒数第k个节点

43 阅读 0 评论 29 点赞

我是靠谱客的博主狂野洋葱，最近开发中收集的这篇文章主要介绍链表中倒数第k个节点，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、需求

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

二、暴力法

2.1 思路分析

确定链表的长度；
定位倒数第k个位置，返回当前结点。

2.2 代码实现

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p = head;
        int count = 0;
        while(p != null) {
            count++;
            if(count == listLength(head) - k + 1) {
                return p;
            }
            p = p.next;
        }
        return null;
    }
    //该方法求链表的长度
    public int listLength(ListNode head) {
        ListNode p = head;
        int count = 0;
        while(p != null) {
            count++;
            p = p.next;
        }
        return count;
    }
}

2.3 复杂度分析

时间复杂度为O(n)；
空间复杂度为O(1)；

三、双指针法

3.1 思路分析

定义前指针former、后指针 latter，均指向head；
前指针former先向前走k步，结束后，后指针latter和前指针former间隔k步；
利用循环，前、后指针共同向后移动，每次循环向后移动一步，直到前指针走过链表尾结点时退出；
因为前后指针相距k步，当前指针退出后，后指针距离尾结点k-1步，那么当前后指针所在的位置就是倒数第k个结点；

3.2 代码实现

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode former = head;
        ListNode latter = head;
        int i = 0;
        while(i < k) {
            if(former == null) return null;
            former = former.next;
            i++;
        }
        while(former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }
}

3.3 复杂度分析