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

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

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

看到题解中有许多做法，但是很多都违背题目本意。
题目考察有：

考察参赛者构建链表能力；
考察参赛者使用链表的能力。

违背本意的做法有：

不构建链表，使用其他容器;
倒序构建链表，为查找倒数第k个节点抄近路；
记住链表长度n，查找第n-k个节点。

但本题必须要(1)正序构建链表;(2)构建后要忘记链表长度。
这里使用递归查找倒数第k个链表：

#include<iostream>
using namespace std;

struct ListNode{
    int m_nKey;
    ListNode* m_pNext;
    ListNode():m_nKey(0),m_pNext(nullptr){};
    ListNode(int x):m_nKey(x),m_pNext(nullptr){};
};

ListNode* getNode(ListNode* node, int& node_num){
    if(node==NULL) return NULL;
    ListNode* head=getNode(node->m_pNext,node_num);
    if(--node_num==0) return node;
    else return head;
}

int main(){
    int node_num,node;
    while(cin>>node_num){
        ListNode* head=new ListNode();//正序构建链表
        ListNode* pre_head=head;
        while(node_num--){
            cin>>node;
            ListNode* next=new ListNode(node);
            head->m_pNext=next;
            head=next;
        }
        cin>>node_num;
        ListNode* rec=getNode(pre_head->m_pNext,node_num);//忘记链表长度，递归找到指定节点
        if(rec!=NULL) cout<<rec->m_nKey<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

全部评论

推荐最新楼层

等人群散尽

楼主

西安电子科技大学 C++

使用双指针，让快指针先走k然后两个指针一块走，当快指针到终点时，慢指针就是目标点

22 回复分享

发布于 2021-07-04 00:35

Vaishya

广东工业大学 C++

该题解秒就妙在node_num是引用。看懂这个引用就能看懂为什么递归能找到倒数的第k个节点

3 回复分享

发布于 2023-02-27 17:04 广东

虚戈戈

电子科技大学 C++

原来是这样！要主动忘掉一些条件

点赞回复分享

发布于 2022-01-08 20:12

牛客836997566号

中山大学 C++

#include <iostream> using namespace std; struct ListNode { int m_nKey; ListNode *m_pNext; ListNode() : m_nKey(0), m_pNext(nullptr){}; ListNode(int x) : m_nKey(x), m_pNext(nullptr){}; }; ListNode *searchNode(ListNode *head, int &node_num) { int i = 0; ListNode *node_i = head; ListNode *node_ii = head; for (; i < node_num; i++) { if (!node_i->m_pNext) { return NULL; } node_i = node_i->m_pNext; } while (node_i) { node_ii = node_ii->m_pNext; } return node_ii; } int main() { int node_num, node; while (cin >> node_num) { ListNode *head = new ListNode(); //正序构建链表 ListNode *pre_head = head; while (node_num--) { cin >> node; ListNode *next = new ListNode(node); head->m_pNext = next; head = next; } cin >> node_num; res = searchNode(pre_head, node_num); done: if (res != NULL) cout << res->m_nKey << endl; else cout << "0" << endl; } return 0; }</iostream>

点赞回复分享

发布于 2022-03-06 08:19

十里坡剑神1024

广西大学 C++

你这并不是C++，完全没用到C++的特性，只是个套C++壳的C。快慢指针有什么难的，既然是C++的单向链表就要用std的forward_list。

点赞回复分享

发布于 2023-06-08 19:23 北京

轻内核可扩展

中山大学测试工程师

学到了，谢谢大佬。

点赞回复分享

发布于 2023-12-05 23:30 广东