剑指Offer-链表中倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

思路

为了能够只遍历一次就能找到倒数第k个节点,可以定义两个指针:

  1. 快指针从链表的头指针开始遍历向前走k-1,慢指针保持不动;
  2. 从第k步开始,慢指针也开始从链表的头指针开始遍历;
  3. 由于两个指针的距离保持在k-1,当快指针到达链表的尾结点时,慢指针正好是倒数第k个结点。

下图是找到该链表的倒数第3个结点的示意图。

代码实现

package LinkedList;

/**
 * 链表中倒数第k个结点
 * 输入一个链表,输出该链表中倒数第k个结点。
 */
public class Solution50 {

    /**
     * 设链表的长度为 N。设两个指针 fast 和 slow,先让 fast 移动 k-1 个节点,则还有 N - k 个节点可以移动。此时让 fast 和 slow 同时移动,可以知道当 fast 移动到链表结尾时,slow 移动到 N - k + 1 个节点处,该位置就是倒数第 k 个节点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode fast = head;
        ListNode slow;
        for (int i = 0; i < k - 1; i++) {
            if (fast.next != null) {
                fast = fast.next;
            } else {
                return null;
            }
        }
        slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

游戏开发 - Math对象相关知识讲解

前几期小编给大家总结了JavaScript的基础知识,为我们后期深入学习JS打下了一定的基础。在后面的几期文章当中我们要来进行JS小游戏的开发,但是开发小游戏的...

29710
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

3125
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

2806
来自专栏算法channel

1800字普林斯顿大学课程浓缩笔记:程序员必知的算法之查找和排序算法

老生常谈,偶尔遇到阐述这两类问题相关的极好素材,它们结合示意图,言简意赅,清晰明了。故分享出来。

760
来自专栏wym

树状数组理论基础

  树状数组(binary indexed trees,二进制索引树),最早由Peter M. Fenwick于1994年以“A New Data Struct...

872
来自专栏简书专栏

基于Excel2013的文本函数

CONCATENATE函数既能引用一个区域直接合并,又不会漏掉数值、日期和公式结果,还能引用多个区域,比&符号更好用。

1104
来自专栏Bingo的深度学习杂货店

从M走到N最少步数

假设一个人站在 X 轴的正半轴上,起始点在 M 点(0 <= M <= 100000),他每次可以向左走一步,向右走一步,或者走到所在坐标乘以2的位置,最终来到...

802
来自专栏GIS讲堂

geotools中等值面的生成与OL3中的展示

本文讲述如何在geotools中IDW插值生成等值面,并根据给定shp进行裁剪,并生成geojson数据,以及Openlayers3中展示。

2075
来自专栏小二的折腾日记

剑指offer-刷题总结

分析:由于每一行都有递增的特性,我们可以采用类似二分搜索的方法。将数组分成行列来进行搜索。

7012
来自专栏小樱的经验随笔

从零开始学建树(树的分治,树的重心)

分治算法在树的路径问题中的应用 一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。 任一个具有n个节点的连通路,它的任何一棵树的树枝数为n-1 分治:...

2634

扫码关注云+社区

领取腾讯云代金券