带你快速刷完67道剑指offer

这是四则或许对你有帮助的讯息

1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档,其中包括往届补录应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新,帮忙扩散一下。

2、😍 免费分享阿秀个人学习计算机以来的收集到的免费资源,点此白嫖

3、🚀如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人踩过的坑留下的经验,事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子,一个人踽踽独行真的不如一群人报团取暖,过去22届和23届的小伙伴好好跟着走下去的,最后基本都拿到了不错的offer!如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话,可以点此下载

# No14、 链表中倒数第k个结点

牛客网原题链接 (opens new window)

# 题目描述

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

# 示例1

输入

1,{1,2,3,4,5}
1

返回值

{5}
1

# 1、比较简单的一种方法

时间复杂度较高,没有二刷的那种方法好

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        int count=0;
        ListNode * node=pListHead;
        while(pListHead!=nullptr){
            count++;
            pListHead=pListHead->next;
        }
        count = count-k;
        if(count<0) return nullptr;
        while(count--)
            node=node->next;
        return node;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

# 二刷:

# 1、快慢指针,不应该说是先后指针

3 ms 376K

    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode * slowNode = pListHead;
        while(k != 0){//这里判断 k 一直走到 0 即可
            k--;
            if(pListHead != nullptr) pListHead = pListHead->next;//在其中判断是否出现k 大于链表总长度的情况,
            //比如 【1,2,3,4,5】 6这样的情况,如果出现这样的情况,返回即可
            else
                return nullptr;
        }
        
        while(pListHead != nullptr){//先走的不能为空
            slowNode = slowNode->next;
            pListHead = pListHead->next;
        }
        return slowNode;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17