求链表倒数第k个结点

题目：输入一个单向链表（只有指向下一个结点指针），输出链表中的倒数第k个结点。

分析：

1. 一个单向链表只有指向下一个结点的指针，所以我们无法得到前面一个结点的指针，所以不能通过最朴素的枚举法来求出。

2. 现在要求出倒数第k个结点。现在用一个指针枚举是无法求出，但是我们可以使用两个指针法（非常重要）。

   初始化设置两个指针p1和p2，p1和p2都指向链表的头结点。我们可以先让指针p1指针先走到第k个结点，下一步开始两个指针p1和p2一起走，当p1指向链表最后一个结点的时候p2指向即为倒数第k个结点。

   为什么呢这个方法是正确的？

   当p1指向第k个结点的时候，p2和p1相差k个结点，所以当p1指向尾结点的时候，p2指向的即为倒数第k个结点。

代码：

[cpp] view plaincopy

//链表结点  

struct ListNode{  

    int value;  

    ListNode *nextNode;  

};   

  

//求倒数第k个结点  

ListNode* GetKthFromTail(ListNode *headNode, int k){  

    //数据不合法  

    if((headNode == NULL) || (k <= 0)){  

        return NULL;  

    }   

    ListNode *p1 = headNode;  

    ListNode *p2 = headNode;  

    int count = 1;  

    //让p1先走到第k个结点  

    while((count < k) && (p1 != NULL)){  

        p1 = p1->nextNode;  

        ++count;  

    }   

    //判断数据合法性  

    if(p1 == NULL){  

        return NULL;  

    }   

    //两个指针一起走，当p1指向尾结点是p2指向即为倒数第k个结点   

    while(((p1->nextNode) != NULL)){  

        p1 = p1->nextNode;  

        p2 = p2->nextNode;  

    }  

    return p2;  

}   

总结

以上是生活随笔为你收集整理的求链表倒数第k个结点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。