剑指Offer第14题：链表中倒数第k个结点

发表于 更新于 分类于

题目：输入一个链表，输出该链表中倒数第k个结点。

解题思路：最直接的思路是，先遍历一遍链表，得出链表的长度，然后计算出倒数第k个结点的正数位置，之后二次遍历链表并输出结果。更好的解法是：设置快慢两个指针，快指针先走k步，然后慢指针开始走，当快指针遍历完链表的时候，慢指针所在的位置即为倒数第k个结点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if (pListHead == NULL || k<=0 ) return NULL; //排除空链表和k<=0的情况
    ListNode* fast = pListHead;
    ListNode* slow = pListHead;
    int cnt = 0;
    while (true) {
        fast = fast -> next;
        cnt += 1;
        if (fast == NULL) {
            if (cnt < k) return NULL; // 当快指针走完链表时，此时cnt即为链表的长度，cnt小于k说明超出链表的范围
            return slow; //不超出则返回慢指针所指的位置
        }
        if (cnt >= k) slow = slow -> next; //当快指针走了k步，慢指针开始走
    }
}