剑指offer：链表倒数第k个节点

题目：输入一个链表，输出该链表的倒数第k个节点，假设从1开始计算，链表的尾节点是倒数第一个节点。

基本思想：

如果只能遍历一次链表就能得到链表的倒数第k个节点就好了，为了实现这个功能，我们定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动，从第k步开始，第二个指针也开始从链表的头指针开始遍历，由于两个指针的距离保持k-1，当第一个指针到达链表尾时，第二个指针正好是倒数第k个节点。

我们要额外考虑的三种情况：

1、输入的  list  为空指针，这在代码中要判断

2、输入的  list  中节点个数不超过k，这时得不到倒数dik个节点

3、输入的 k=0或者为负数，这时候也不会出来任何结果

ListNode* FindKthToTail(ListNode *pListHead,int k)
{
    if(pListHead==NULL || k<=0)return NULL;
    ListNode *p1=pListHead,*p2=NULL;
    int i=0;
    for(i=0;i<k-1;++i)
    {
        if(p1->next!=NULL)
            p1=p1->next;
        else
            return NULL;
    }
    p2=pListHead;
    while(p1->next != NULL)
    {
        p1=p1->next;
        p2=p2->next;
    }
    return p2;
}

上面的程序处理了3中可能出现的异常情况，这是代码健壮性的体现，

PS：

1、求链表的中间节点，如果链表中节点总数为奇数，返回中间节点；总数是偶数，返回中间两个节点的任意一个。我们可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，一个指针一次走两步，当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。当然这过程中也要考虑一些额外的情况防止出现意外。

2、判断一个单向链表是否形成环形结构。定义两个指针，同时从链表的头节点出发，一个指针一次走一步，一个指针一次走两步，如果走得快的的指针追上了走的慢的指针，那么链表就是环形链表，如果走得快的指针一直追到了链表的末尾都没有赶上走的慢的指针，那么链表就不是环形链表。

剑指offer：链表倒数第k个节点,布布扣,bubuko.com

剑指offer：链表倒数第k个节点

原文：http://blog.csdn.net/litianpenghaha/article/details/23875375