/*

第 13 题（链表）：

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

的尾指针。

链表结点定义如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

start time = 20:40

end time

*/

#include <stdio.h>

#include <stdlib.h>

typedef struct ListNode

{

    int m_nKey;

    ListNode* m_pNext;

}ListNode;

ListNode * reverseList(ListNode * L)

{

    ListNode * pp = L;

    ListNode * p = L->m_pNext;

    pp->m_pNext = NULL;

    while (p != NULL)

    {

        ListNode * p3 = p->m_pNext;

        p->m_pNext = pp;

        pp = p;

        p = p3;

    }

    return pp;

}

ListNode * getKthNodeFromBack(ListNode * L, int k)

{

    if(k == )

        return NULL;

    ListNode * rL = reverseList(L);

    ListNode * p = rL;

    for (int i = ; p != NULL && i < k-; i++) //注意检测k不能超过链表长度，否则返回NULL

    {

        p = p->m_pNext;

    }

    reverseList(rL);

    return p;

}

void displayList(ListNode * L)

{

    ListNode * p = L;

    while (p != NULL)

    {

        printf("%d ",p->m_nKey);

        p = p->m_pNext;

    }

    printf("\n");

}

void createList(ListNode * &L)

{

    int d;

    scanf("%d",&d);

    if (d != )

    {

        L = (ListNode *)malloc(sizeof(ListNode));

        L->m_nKey = d;

        L->m_pNext = NULL;

        createList(L->m_pNext);

    }

}

int main()

{

    ListNode * L = NULL;

    createList(L);

    ListNode * pk = getKthNodeFromBack(L, );

    displayList(L);

    return ;

}

LinkList.h 

#ifndef LINKLIST_H

#define LINKLIST_H

#include <stdlib.h>

#include <stdio.h>

#include <iostream>

using namespace std;

typedef struct node{

int val;

struct node *next;

}node,*pNode;

pNode CreateLinkList(pNode &T);

pNode FindLastKth(pNode T,int k);

#endif

LinkList.cpp

#include "LinkList.h"

pNode CreateLinkList(pNode &T){

int ival;

cin>>ival;

if(ival==)

return NULL;

T = (pNode)malloc(sizeof(node));

T->val = ival;

T->next = NULL;

T->next = CreateLinkList(T->next);

return T;

}

pNode FindLastKth(pNode T,int k){

pNode low=T,fast = T;

for(int i=;i<k&&fast!=NULL;i++){

fast = fast->next;

}

if(fast == NULL)

return NULL;

while(fast!=NULL){

fast = fast->next;

low = low->next;

}

return low;

}

Main.cpp

#include "LinkList.h"

void main(){

pNode T;

T = NULL;

CreateLinkList(T);

int k=;

pNode pnode;

pnode = FindLastKth(T,k);

cout<<pnode->val;

system("pause");

}