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

题目描述

输入一个链表，输出该链表中倒数第k个结点。
例如：
输入链表：1->2->3->4->5->6->7，k = 3
输出链表：5->6->7

题解：

首先获取链表总长度len；然后让链表的头节点指针head右移len-k次，就能得到倒数第k个节点啦。
注：记得考虑边界值k=len！这种情况，我们要输出NULL，不然是通过不了滴！
My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int GetLongNode(ListNode *head) {
    int len = 0;
    while (head) {
        head = head->next;
        len += 1;
    }
    return len;
}

class Solution {
public:
    ListNode * FindKthToTail(ListNode* pListHead, unsigned int k) {
        int len = GetLongNode(pListHead);
        int dect_len = len - k;
        if (dect_len >= len || dect_len < 0) {
            return NULL;
        }
        while (dect_len) {
            pListHead = pListHead->next;
            dect_len -= 1;
        }
        return pListHead;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    Solution s;
    ListNode *result = s.FindKthToTail(&a, 3);
    while (result) {
        printf("%d->", result->val);
        result = result->next;
    }
    return 0;
}

结果：

5->6->7->