牛客华为机试题 --求链表的倒数第k个元素

题目描述

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

链表结点定义如下：

struct ListNode

{

int       m_nKey;

ListNode* m_pNext;

};

详细描述：

接口说明

原型：

ListNode* FindKthToTail(ListNode* pListHead, unsignedint k);

输入参数：

ListNode* pListHead  单向链表

unsigned int k  倒数第k个结点

输出参数（指针指向的内存区域保证有效）：

无

返回值：

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

虽然很迷，在codeblocks上输入样例没错，但牛客就是通不过。不过还是决定记录下来

思路：先创建链表，从头开始数到k个。两个指针一个指向第一个元素，另一个指向第k个。然后两个指针移动。有点滑动窗口的思想。刚才指向第k个的指针后移到最后一个的时候，头指针就指向倒数第k个了。

#include<iostream>
using namespace std;
int N;
struct ListNode
{
    int m_nkey;
    ListNode* m_pNext;
};
void creat(ListNode* pListHead,int data[],int n)
{
    ListNode* head=pListHead;
    for(int i=1;i<n;i++)
    {
        ListNode* l=new ListNode;
        l->m_nkey=data[i];
        pListHead->m_pNext=l;
        pListHead=l;
    }
    pListHead->m_pNext=NULL;
    pListHead=head;
}
int main()
{
    cin>>N;
    int data[N];
    for(int i=0;i<N;i++)
    {
        cin>>data[i];
    }
    int k;
    ListNode* head=new ListNode;
    head->m_nkey=data[0];
    creat(head,data,N);
    cin>>k;
    ListNode *node=head;
    ListNode *p;
    int count=0;
    for(;node!=NULL;node=node->m_pNext)
    {
        count++;
        if(count==k)
        {
            p=node;
            break;
        }
    }
    node=head;
    for(int i=k-1;i<N-1;i++)
    {
       node=node->m_pNext;
    }
    cout<<node->m_nkey<<endl;


}

 

 迷惑。。。