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

题目描述

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

思路

假如结点数是 n，倒数第 k 个结点也就是正数第 n - k + 1 个结点。

1. 定义两个指针，p 和 q，p 先走 k - 1 步。
2. 然后 p 和 q 同时走，直到 p 走到结尾，这时候 p 和 q 共同走了 n - (k - 1) 步，也就是 n - k + 1。因此这时候的 q 就是我们所求的。

注意项:

• 链表为空或者 k 为 0 时，返回空。
• k 大于链表的长度，返回空。

代码

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL || k == 0)
        {
          return NULL;  
        }
        ListNode* p;
        ListNode* q;
        p = pListHead;
        q = pListHead;
        k--;
        while(k--)
        {
            if(p->next != NULL)
            {
                p = p->next;
            }
            else
            {
                return NULL;  
            }
        }
        while(p->next != NULL)
        {
            p = p->next;
            q = q->next;
        }
        return q;
    }
};