ACM. Hj51 outputs the penultimate node ●

HJ51 Output the penultimate... In the one-way linked list k Nodes ●

describe

Enter a one-way linked list , Output the last number in the list k Nodes , The bottom of the list 1 The first node is the tail pointer of the linked list .

The definition of linked list node is as follows ：

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

Return to the penultimate... Normally k individual Node pointer , Exception return Null pointer .

requirement ：
(1) Build a linked list in positive order ;
(2) After construction Forget the length of the linked list .
Data range ： The length of the linked list meets $1\le n\le 1000$, $k\le n$, The data in the linked list meets $0\le val\le 10000$

This topic has Multiple sets of sample input .

Input description ：

Enter description

1. Enter the number of linked list nodes
2. Enter the value of the linked list
3. Input k Value

Output description ：

Output an integer

Example

Input ：
8
1 2 3 4 5 6 7 8
4
Output ：
5

Answer key

1. Speed pointer

Multiple sets of test cases , Output in each cycle cout that will do .

Use the speed pointer to count down k The judgment of number ：
A fast pointer is faster than a slow pointer k Step , When the fast pointer comes null Node time , The slow pointer now points to the penultimate k Number .

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

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

int main(){
    
    int n, k, num;
    while(cin >> n){
            //  Number of nodes for multiple groups of use cases 
        ListNode* dummyHead = new ListNode(); 	//  Virtual head node 
        ListNode* pre = dummyHead;
        for(int i = 0; i < n; ++i){
                 //  Create a one-way linked list 
            cin >> num;
            ListNode* curr = new ListNode();
            pre->m_pNext = curr;
            curr->m_nKey = num;
            pre = curr;
        }
        cin >> k;
        ListNode *slow = dummyHead->m_pNext;    //  Speed pointer 
        ListNode *fast = dummyHead->m_pNext;
        if(k == 0){
    								//  Last but not least 0 Number , prune 
            cout << 0 << endl;
        }else{
    
            for(int i = 0; i < k; ++i){
            	//  A fast pointer is faster than a slow pointer k Step 
                fast = fast->m_pNext;
            }
            while(fast != nullptr){
                 //  When the fast pointer comes null Node time 
                slow = slow->m_pNext;
                fast = fast->m_pNext;
            }
            cout << slow->m_nKey << endl;       //  Output slow node 
        }      
    }
    return 0;
}