题解 | #输出单向链表中倒数第k个结点#

输出单向链表中倒数第k个结点

https://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d

#include <climits>
#include <iostream>
using namespace std;

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

ListNode* fun(ListNode* q,int& num)
{
    if(q==NULL) return NULL;
    ListNode* p=fun(q->m_pNext,num);
    //在找到指定结点前p一直返回NULL,在找到后由于将q返回给上一层p故之后p一直返回指定节点
    if(--num==0)    return q;
    else return p;
}

int main() {
    int n,temp;
    while(cin>>n)//数据节点个数
    {
        ListNode* head=new ListNode({INT_MAX,NULL});//创建起始节点
        ListNode* last=head;//建立尾指针,利用尾插法建立链表
        for(int i=0;i<n;i++)//创建链表
        {
            cin>>temp;
            ListNode* p=new ListNode({temp,NULL});//建立数据节点
            last->m_pNext=p;
            last=last->m_pNext;//移动指针到最新结点
        }
        cin>>n;//倒数第几个结点
        ListNode* node=fun(head->m_pNext,n);//调用递归找到对应节点
        cout<<node->m_nKey<<endl;;
    }
    
    
}
// 64 位输出请用 printf("%lld")

全部评论
递归开销爆炸,我想了想这个问题是有复杂度n+k/2+2n/k或者n+3k/2+n/k的方法的,当然最笨的2n-k也够用
点赞 回复 分享
发布于 2023-06-12 21:03 北京

相关推荐

05-09 14:45
门头沟学院 Java
点赞 评论 收藏
分享
AI牛可乐:哇塞,恭喜恭喜!48万的年薪,真是让人羡慕呀!看来你找到了一个超棒的工作,可以享受不卷的生活啦!🎉有没有什么求职秘诀想要分享给小牛牛呢?或者,想不想知道我是谁呢?😉(点击我的头像,我们可以私信聊聊哦~)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务