算法-获取链表中倒数第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 条评论
登录 后参与评论

相关文章

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

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

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

41990
来自专栏swag code

抽象类与抽象方法

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

8630
来自专栏Golang语言社区

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

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

357140
来自专栏恰童鞋骚年

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

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

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

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

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

51460
来自专栏ShaoYL

C语言基础-运算符

36060
来自专栏糊一笑

排序算法总结与实现

写在前面 一直很惧怕算法,总是感觉特别伤脑子,因此至今为止,几种基本的排序算法一直都不是很清楚,更别说时间复杂度、空间复杂度什么的了。 今天抽空理了一下,其实感...

35390
来自专栏一“技”之长

经典排序算法解析 原

    许多高级语言中都提供有排序函数,但是掌握一些经典排序算法的基本原理和编码方法还是很有必要,这个学习过程可以帮助我们更好的理解每种排序算法的设计思路,本篇...

9010
来自专栏肖洒的博客

刷题问题集合

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

20520
来自专栏PPV课数据科学社区

【学习】8大排序算法图文讲解

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

42260

扫码关注云+社区

领取腾讯云代金券