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

相关文章

来自专栏Golang语言社区

Go语言的fmt包中文教程

Fmt包 import "fmt" 简介 ▾ Package fmt包含有格式化I/O函数,类似于C语言的printf和scanf。格式字符串的规则来源于C但更...

2326
来自专栏desperate633

深入理解javascript中的继承机制(4)多继承寄生式继承借用构造函数借用构造函数并且复制原型以上

我们知道多继承是面向对象的语言中比较纠结的一个问题,有好处也存在缺陷。这方面我们不多讨论。就javascript而言,要实现多继承是比较简单的,因为javasc...

641
来自专栏進无尽的文章

Swift| 基础语法(二)

总结下 swift下的基础语法,里面涉及到:常量&变量、Swift中的数据类型、逻辑分支、循环、字符串相关、数组和字典、方法的书写调用等内容,考虑到阅读体验分多...

582
来自专栏女程序员的日常

快慢指针

一、快慢指针说明   快慢是指移动步数的长短,也就是每次向前移动速度的快慢。如,指定快指针每次沿着链表向前移动2步,指定慢指针每次沿着链表向前移动1步。 二、快...

2561
来自专栏老九学堂

【超全】C语言小白最容易犯的17种错误,你中了几个?

C编译的程序对语法检查并不像其它高级语言那么严格,这就给编程大佬们留下了“灵活的余地”,但还是由于这个灵活给程序的调试带来了许多不便,尤其对刚刚接触C语言的人来...

3295
来自专栏和蔼的张星的图像处理专栏

112. 删除排序链表中的重复元素比较删除

给定一个排序链表,删除所有重复的元素每个元素只留下一个。 样例 给出 1->1->2->null,返回 1->2->null 给出 1->1->2->3-...

482
来自专栏尾尾部落

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

经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

732
来自专栏一个会写诗的程序员的博客

第2章 Kotlin 语法基础第2章 Kotlin 语法基础

人与人之间通过语言来交流沟通,互相协作。人与计算机之间怎样“交流沟通”呢?答案是编程语言。一门语言有词、短语、句子、文章等,对应到编程语言中就是关键字、标识符、...

1002
来自专栏机器学习实践二三事

leetcode之-题19

题目 [图片] Given a linked list, remove the nth node from the end of list and re...

1847
来自专栏进击的君君的前端之路

字符串与JSON

1363

扫码关注云+社区