算法-获取链表中倒数第k个结点

题目: 输入一个链表,输出该链表中的倒数第k个结点。比如链表中的值为1,2,3,4,5,6。倒数第三个结点为值为4的结点。链表定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路: 这个问题相对来说还是挺好理解的,要找到倒数第k个结点,最直接的思路肯定是倒着数k个结点不就好了,但是问题是链表不能从尾结点开始遍历,只能从头结点开始。 那么倒数第k个的问题基于必须要转化成正数第n-k+1个,其中n是整个链表的长度,那么问题就可以这样解决: (1)先遍历一遍链表,得到链表的长度n; (2)再从头遍历链表,遍历到n-k+1个就是要找到的倒数第k个结点。 但是这种方法必须要遍历两次,那么有没有遍历一次就得到正确结果的方法呢? 可以通过定义两个指针,第一个指针p1先走k-1步后第二个指针p2再开始走,到k步时两个指针同步走,那么当p1到底链表的结尾时,p2正好走到了第k个结点。

此时这种方法牺牲了空间复杂度(两个指针),换来了时间复杂度的降低,这也是设计算法时比较常用的方式—“用空间换时间”。

代码实现:

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
    if(pListHead == NULL || k == 0)
        return NULL;

    ListNode *pAhead = pListHead;
    ListNode *pBehind = NULL;
    for(unsigned int i = 0; i < k - 1; ++ i)
    {
        if(pAhead->next != NULL)
            pAhead = pAhead->next;
        else
        {
            return NULL;
        }
    }
    pBehind = pListHead;
    while(pAhead->next != NULL)
    {
        pAhead = pAhead->next;
        pBehind = pBehind->next;
    }
    return pBehind;
}

上述代码具有较好的鲁棒性: (1)如何输入的 *pListHead 为空,程序返回null而不会异常。 (2)如果输入链表 *pListHead长度小于k个,程序返回null而不会异常。(一个小于k个长度的链表显然没有倒数第k个结点) (3)如果输入的k=0,代码不会异常,而是返回null。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

常用排序算法总结(1)

1132
来自专栏C/C++基础

十种常见排序算法

十种常见排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择...

871
来自专栏swag code

抽象类与抽象方法

在我们抽象实例对象的时候,有这样一种情况,往上层抽象时就会发现很难描述对象的属性和行为,比如“形状” ,其方法计算面积怎么计算?正方形知道怎么计算,长方形也知道...

743
来自专栏Python爬虫与算法进阶

Leetcode-Solutions 1.two-sum (Python&Golang)

恩,最后找队友一起刷题。喜欢可以联系我 ,来公众号“Python爬虫与算法进阶”找我哦

3889
来自专栏Java Edge

Collections.sort()源码分析(基于JAVA8)java.lang.Object java.util.Collections简介Collections的sort方法代码:TimSort.

36912
来自专栏恰同学骚年

剑指Offer面试题:2.二维数组中的查找

  例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。

882
来自专栏Java技术栈

涨姿势,图文带你了解 8 大排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

1025
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day09-重构随机点名器

Java基础-day09-重构随机点名器 1.案例介绍与演示 随机点名的案例由之前简单的Person对象,重构为相对完整的Person对象并使用。 2.案例回顾...

3916
来自专栏肖洒的博客

刷题问题集合

split()通过指定分隔符对字符串进行切片,如果参数num有指定值,则仅分隔 num 个子字符串. usage; str.split(str=””, num=...

1242
来自专栏Golang语言社区

Golang语言社区--【基础知识】常量

常量是指该程序可能无法在其执行期间改变的固定值。这些固定值也被称为文字。 常量可以是任何像一个整型常量,一个浮点常量,字符常量或字符串文字的基本数据类型。还有枚...

3205

扫码关注云+社区