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

相关文章

来自专栏mathor

KMP(4)

895
来自专栏python3

python 生成器

第一种方法很简单,只要把一个列表生成式的[]改成(),就创建了一个generator:

841
来自专栏蜉蝣禅修之道

LeetCode之Intersection of two linked list不同方法

812
来自专栏C语言及其他语言

【蓝桥杯系列】第一节 C的基本用法

置顶编程范收获更多热门编程快讯 大家好,最近很多小伙伴向我反应小编!我参加了蓝桥杯但是我连那是什么都不知道,我该怎么训练?是不是在网站刷题就可以啊? 在这里我要...

3167
来自专栏武培轩的专栏

剑指Offer-二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 思路 思路一: 由于要求链表是有序...

2613
来自专栏于晓飞的专栏

读 Java TimSort算法 源码 笔记

本来准备看Java容器源码的。但是看到一开始发现Arrays这个类我不是很熟,就顺便把Arrays这个类给看了。Arrays类没有什么架构与难点,但Arrays...

742
来自专栏King_3的技术专栏

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

1033
来自专栏有趣的Python

玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set...

3296
来自专栏aoho求索

由散列表到BitMap的概念与应用(一)

散列表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触散列表时,它的优点多得让人难以置信。不论散列表中有多少数据,插入和删除只需要接近常量的时间即O...

592
来自专栏猿人谷

查找链表中倒数第k个结点

题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下: struct ListNode { in...

1955

扫码关注云+社区