数据结构与算法面试题80道（13）

第13题:

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

链表结点定义如下: 

struct ListNode

{

 int m_nKey;

 ListNode* m_pNext;

};

 思路：我用的最笨的办法，先统计长度，在遍历去找，O（2n）

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

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

void addNode(ListNode *&mList,int value){
    if(mList==NULL){
         ListNode *_list=new ListNode();
         if(_list==NULL) {cout<<"内存错误"<<endl;return;}
        _list->m_nKey=value;
        _list->m_pNext=NULL;
        mList=_list;
    }else addNode(mList->m_pNext,value);
}

ListNode* fun_k(ListNode *mList,int k){
    int len=0;
    ListNode *p=mList;
    while(p!=NULL){
        len++;
        p=p->m_pNext;
    }
    if(k>len) return NULL;
    p=mList;
    for(int i=0;i<len-k;i++)
        p=p->m_pNext;
    return p;
}

int main(){

    ListNode *head=NULL;
    addNode(head,1);
    addNode(head,2);
    addNode(head,3);
    addNode(head,4);
    addNode(head,5);
    addNode(head,6);
    addNode(head,7);
    ListNode *p=new ListNode();

    int k=3;
    p=fun_k(head,k);
    cout<<"list 的倒数第K个结点是："<<p->m_nKey<<endl;
    return 0;
}