BM8、链表中倒数最后k个结点

牛客网新出了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。

题单地址：https://www.nowcoder.com/link/pc_kol_wsx

一、题目描述

输入一个长度为 n 的链表，设链表中的元素的值为 a_i ，返回该链表中倒数第 k 个节点。

如果该链表长度小于 k，请返回一个长度为 0 的链表。

数据范围：0 ≤n≤10^5，0 ≤ a_i ≤10^9，0 ≤k≤10^9

二、题目解析

一般来说，链表相关的算法题考察的知识点有以下几个：

递归
反转
双指针
环

本题解题思路如下：

1、初始化两个指针 former 和 latter，一开始都指向链表的头节点
2、前指针 former 先向前走 k 步
3、两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
4、由于 former 和 latter 之间的距离为 k，所以 latter 指向的节点即是倒数第 k 个节点，最后返回 latter

BM8、链表中倒数最后k个结点

三、参考代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        //初始化两个指针 former 和 latter，一开始都指向链表的头结点

        // 指针 former 指向链表的头结点
        ListNode former = pHead;

        // 指针 latter 指向链表的头结点
        ListNode latter = pHead;

        // 让 former 指针先向前走 k 步
        for (int i = 0 ; i < k; i++) {
            // 根据题目给定的数据范围，k 的值可能会大于链表的结点数量
            // 比如链表结点有 5 个，而 k 的值是 100
            // 那么 former 就有可能指向 null ， 无法继续向后移动了
            // 所以需要做一个边界处理
            if( former == null){
                return null;
            }
            // former 指针向后移动
            former = former.next;
        }

        // 接下来，让这两个指针 former 和 latter 同时向前移动，直到前指针 former 指向 NULL
        while (former != null) {
            // former 指针向后移动
            former = former.next;
            // latter 指针向后移动
            latter = latter.next;
        }

        // 此时，由于 former 和 latter 之间的距离为 k
        // 所以 latter 指向的结点即是倒数第 k 个结点
        return latter;
    }
}

一、题目描述

二、题目解析

三、参考代码

相关文章