c++语言程序设计习题之链表中倒数第n个结点实例代码。输出该链表中的某个结点的实例。

题目来自剑指Offer

语言程序设计习题：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，现在从1开始计数，即链表的尾节点是倒数第一个结点。例如一个链表有6个结点，从结点开始它们的值依次是1、2、3、4、5、6.这个链表的倒数第三个结点是4的结点。

c++链表结点定义方法如下：struct ListNode

{

int m_nValue;

ListNode*  m_pNext;

}

输出该链表结点代码：

#include <iostream>
#include <assert.h>
using namespace std;

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

/*
注意初始化时，快指针应指向第k个结点，慢指针指向第1个结点。
*/
ListNode* FindKthToTail(ListNode* pListHead,unsigned int k)
{
assert(pListHead != NULL && k != 0);
unsigned int i = 1;
ListNode* pFirstNode = pListHead;
ListNode* pSecNode = pListHead;

while (pFirstNode && i <= k)
{
pFirstNode = pFirstNode->m_pNext;
i++;
}

if (i <= k)
{
return NULL;
}

while (pFirstNode)
{
pSecNode = pSecNode->m_pNext;
pFirstNode = pFirstNode ->m_pNext;
}
return pSecNode;
}

void CreateList(ListNode** pHead,int nLen)//头指针使用指针的指针
{
assert(*pHead == NULL && nLen > 0);
ListNode* pCur = NULL;
ListNode* pNewNode = NULL;
for (int i = 0;i < nLen;i++)
{
pNewNode = new ListNode;
cin>>pNewNode->m_Data;
pNewNode->m_pNext = NULL;

if (*pHead == NULL)
{
*pHead = pNewNode;
pCur = *pHead;
}
else
{
pCur->m_pNext = pNewNode;
pCur = pNewNode;
}
}
}

void PrintList(ListNode* pCurNode)
{
assert(pCurNode != NULL);
while (pCurNode)
{
cout<<pCurNode->m_Data<<” “;
pCurNode = pCurNode->m_pNext;
}
cout<<endl;
}

int main()
{
int nLen = 0;
ListNode* pHead = NULL;
cout<<”please input node num: “;
cin >> nLen;
CreateList(&pHead,nLen);//注意传参使用引用
PrintList(pHead);
ListNode* pKthToTail = FindKthToTail(pHead,1);
if (pKthToTail)
{
cout<<”倒数第一个结点:”<<pKthToTail->m_Data<<endl;
}
else
{
cout<<”倒数第一个结点不存在!”<<endl;
}
pKthToTail = FindKthToTail(pHead,5);
if (pKthToTail)
{
cout<<”倒数第五个结点:”<<pKthToTail->m_Data<<endl;
}
else
{
cout<<”倒数第五个结点不存在!”<<endl;
}

pKthToTail = FindKthToTail(pHead,3);
if (pKthToTail)
{
cout<<”倒数第三个结点: “<<pKthToTail->m_Data<<endl;
}
else
{
cout<<”倒数第三个结点不存在!”<<endl;
}
system(“pause”);
return 1;
}

注意事项：

（1）链表里面没有k个结点的情况；

（2）初始化时慢指针指向第一个结点，快指针指向第k个结点。