[剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

题目描述

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

解题思路

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个指针的距离保持在k-1,当第一个指针到达链表的尾节点时,第二个指针刚好指向倒数第k个节点。

关注要点 1. 链表头指针是否为空,若为空则直接返回回null 2. k是否为0,k为0也就是要查找倒数第0个节点,由于计数一般是从1开始的,所有输入0没有实际意义,返回null 3. k是否超出链表的长度,如果链表的节点个数少于k,则在指针后移的过程中会出现next指向空指针的错误,所以程序中要加一个判断

参考代码

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k == 0)
            return null;
        ListNode temp = head;
        //判断k是否超过链表节点的个数,注意是 i < k - 1
        for(int i=0; i < k-1; i++){
            if(temp.next != null)
                temp = temp.next;
            else
                return null;
        }
        ListNode pA = head;
        ListNode pB = head;
        for(int i=0; i<k-1; i++)
            pA = pA.next;
        while(pA.next != null){
            pA = pA.next;
            pB = pB.next;
        }
        return pB;
    }
}

当然,还有一种是用stack的方法,把链表按顺序压入stack,然后直接取出stack的第k个节点。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

761
来自专栏大闲人柴毛毛

剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

/** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

3754
来自专栏mathor

LeetCode164. 最大间距

 这道题用到了桶排序的思想,但是跟排序没啥关系,思路是这样的,数组中有n个元素,那么就构建n+1个桶,桶的属性有三个,最大值最小值以及是否为空。桶的下标从0...

1152
来自专栏ACM算法日常

分割排序(排序)- HDU 1106

输入一行数字,如果我们把这行数字中的‘5’都看成空格,那么就得到一行用空格分割的若干非负整数(可能有些整数以‘0’开头,这些头部的‘0’应该被忽略掉,除非这个整...

781
来自专栏你不就像风一样

让你一看就懂的快速排序算法(Java)

你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需...

1122
来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

972
来自专栏老司机的技术博客

人人都能学会的python编程教程6:列表(list)

当索引超出了范围时,Python会报一个IndexError错误,所以,要确保索引不要越界,记得最后一个元素的索引是len(classmates) - 1。如果...

43210
来自专栏武培轩的专栏

排序算法-插入排序

算法简介 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

2764
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

3676
来自专栏目标检测和深度学习

常用排序算法总结(2)

1364

扫码关注云+社区

领取腾讯云代金券