链表中倒数第k个结点

题目描述

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

思路

• 设置两个指针分别指向第一个结点，先让前指针跑k-1步，使得后指针指向第k个结点。然后同时向前跑。当后指针指向最后一个结点时候停止，即post->next==NULL;

题解

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==NULL || k==0)
            return NULL;
        ListNode * pre = pListHead;
        ListNode * post = pListHead;
        int i = 0;
        while(post!=NULL && i<k-1){
            post = post->next;
            i++;
        } 
        if(post==NULL)
            return NULL;
        while(post->next!=NULL){
            pre = pre->next;
            post = post->next;
        }
        return pre;
    }
};