首页 » C++ » 《剑指Offer》 链表中倒数第k个结点

《剑指Offer》 链表中倒数第k个结点

2017-04-07 12:22:38阅读(242)

题目描述:
输入一个链表,输出该链表中倒数第k个结点

思路:
设置一个新ret,先将pListHead位置往后移k-1位,使得ret与pListHead距离为k-1,这样只要pListHead为最后一个位置时,ret的位置就是倒数第k个节点的位置,返回ret。

代码:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *ret = pListHead;
        unsigned int i = 0;
        /* 向前步进k-1个节点,因为链表个数可能不足,所以需要判断head值是否有效 */
        while (pListHead && i < k-1) {
            ++i;
            pListHead = pListHead->next;
        }
        /* head为NULL的话,说明链表个数不足,返回NULL */
        if (!pListHead) {
            return NULL;
        }
        /* 
        让ret与head同步向后步进,这样保证了ret与head之间的距离为k-1。
        这样当head到达最后一个节点的时候,ret即为所求的值。
        */
        while (pListHead->next) {
            ret = ret->next;
            pListHead = pListHead->next;
        }
        return ret;
    }
};

输出结果:运行时间: <1 ms 占用内存:8552K 状态:答案正确

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹