题目：输入一个链表，输出这个链表中倒数第K个节点。（代码的鲁棒性）
思路：用两个指针p1和p2,都指向头节点，开始的时候，p2不动，p1移动k-1次，指向第k个节点。此时，如果p1->next!=null,则同时移动P1和p2.直到p1指向最后一个节点。此时，P2指向倒数第k个节点。
C++代码：
#include<iostream>
using namespace std;
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};
ListNode* createList(int a[],int k)
{
ListNode* pHead=NULL,*pNode=NULL;
for(int i=;i<k;i++)
{
ListNode* pNew=new ListNode();
pNew->m_nValue=a[i];
pNew->m_pNext=NULL;
if(pHead==NULL)
{
pHead=pNew;
pNode=pNew;
}
else
{
pNode->m_pNext=pNew;
pNode=pNode->m_pNext;
}
}
return pHead;
}
void printList(ListNode* pHead)
{
ListNode* p=pHead;
while(p!=NULL)
{
cout<<p->m_nValue<<" ";
p=p->m_pNext;
}
cout<<endl;
}
ListNode* printKToTail(ListNode* pHead,unsigned int k)
{
if(pHead==NULL||k==)
return NULL;
ListNode* pAhead=pHead;
ListNode* pTail=NULL;
for(int i=;i<k-;i++)
{
if(pAhead->m_pNext!=NULL)
pAhead=pAhead->m_pNext;
else
return NULL;
}
pTail=pHead;
while(pAhead->m_pNext!=NULL)
{
pAhead=pAhead->m_pNext;
pTail=pTail->m_pNext;
}
return pTail;
}
void main()
{
int a[]={,,,,};
ListNode* pHead=createList(a,);
printList(pHead);
ListNode* pKTail=printKToTail(pHead,);
cout<<pKTail->m_nValue<<endl; }
Java代码：鲁棒性的体现：在这个函数printKToTail中，开头对头指针和k值进行判断，for语句中用if语句对总长度小于K值的时候做了判断。
public class PrintKToTail {
public static class ListNode
{
public int m_nValue;
public ListNode m_pNext;
}
//创建链表
public static ListNode CreateLink(int a[],int k)
{
ListNode Head=null,q=null;
for(int i=0;i<k;i++)
{
ListNode pNew=new ListNode();
pNew.m_nValue=a[i];
pNew.m_pNext=null;
if(Head==null)
{
Head=pNew;
q=pNew;
}
else
{
q.m_pNext=pNew;
q=q.m_pNext;
}
}
return Head;
}
//从头到尾打印列表
public static void printLink(ListNode pHead)
{
ListNode p=pHead;
while(p != null)
{
System.out.print(p.m_nValue+" ");
p=p.m_pNext;
}
System.out.println("\n");
}
//输出输出链表的倒数第K个节点
public static ListNode printKToTail(ListNode pHead,int k)
{
if(pHead==null||k<=0)
return null;
ListNode pAhead=pHead;
ListNode pTail=null;
for(int i=0;i<k-1;i++)
{
if(pAhead.m_pNext!=null)
pAhead=pAhead.m_pNext;
else
return null;
}
pTail=pHead;
while(pAhead.m_pNext!=null)
{
pAhead=pAhead.m_pNext;
pTail=pTail.m_pNext;
}
return pTail;
}
public static void main(String[] args)
{
int a[]={1,2,3};
ListNode Head=CreateLink(a,3);
printLink(Head);
ListNode pKTail=printKToTail(Head,2);
System.out.println(pKTail.m_nValue+" ");
}
}
相关题目1：求链表的中间节点。
思路：同样是定义两个指针p1和p2,两给指针同时移动，只是p1指针每次移动一步，p2指针每次移动两步，当p2指向链表的尾部时，p1正好指向中间节点。
相关题目2：判断一个单向链表是否为环状。
思路：同样是定义两个指正p1和p2,两个指针同时移动，当p2能追赶到p1时，表示该单向链表为环状。否则当p2已经走到尾部，而p1还没有追上p2.就代表改单向链表不为环状。