描述

输入一个单向链表,输出该链表中倒数第k个结点,链表的倒数第1个结点为链表的尾指针。

链表结点定义如下:

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

正常返回倒数第k个结点指针,异常返回空指针。

要求:

(1)正序构建链表;

(2)构建后要忘记链表长度。

数据范围:链表长度满足 1≤n≤1000  , k≤n  ,链表中数据满足 0≤val≤10000 

本题有多组样例输入。

输入描述:

输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值

输出描述:

输出一个整数

示例1

输入:

8
1 2 3 4 5 6 7 8
4

输出:

5

AC code

/// HJ51 输出单向链表中倒数第k个结点
#include <bits/stdc++.h>
using namespace std;

// 定义ListNode的结构
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
    ListNode(): m_nKey(0), m_pNext(nullptr) {};
    ListNode(int x): m_nKey(x), m_pNext(nullptr) {};
};

// 使用递归逆序查找倒数第node_pos个节点
ListNode* searchNode(ListNode* node, int& node_pos)
{
    if(node==NULL) return NULL;
    ListNode* head = searchNode(node->m_pNext, node_pos);
    if(--node_pos==0) return node;
    else return head;
}

int main()
{
    // 输入node_num个节点,每个节点的值存进node_key
    int node_num, node_key;
    while(cin>>node_num)
    {
        ListNode* head = new ListNode();
        ListNode* preHead = head;
        while(node_num--)
        {
            cin>>node_key;
            ListNode* next = new ListNode(node_key);  // 正序构建链表
            head->m_pNext = next;
            head = next;
        }

        // 输入查找的节点:倒数第node_pos个节点
        int node_pos;
        cin>>node_pos;
        ListNode* res = searchNode(preHead, node_pos);  // 忘记链表长度,递归找到指定节点
        if(res!=NULL) cout<<res->m_nKey<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

关于参数传递int& node_pos的详解:

参数传递过程中:函数形参 int a 与 int& a 的区别_CH_whale的博客-CSDN博客


版权声明:本文为CH_whale原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/CH_whale/article/details/127338794