1.4 链表中倒数第k个结点

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

怎么说呢，我能想到的方法感觉特别low，遍历一遍得到总数sum，然后从前到后找第sum - k + 1个

注意当k > sum时，返回的是NULL，这个不等价于返回ListNode* r = new ListNode(0);

而且这个题最后返回的也不是单纯的一个结点啊。

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* h = pListHead;
        int sum = 0;
        while(h != NULL){
            sum++;
            h = h -> next;
        }
        if(k > sum){
            return NULL;
        }
        int n = sum - k;
        h = pListHead;
        while(n--){
            h = h -> next;
        }
        return h;
    }
};

果然评论区有大神直接，膜拜一下~

两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指针走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。。看时间复杂度的话好像没什么差，所以。。

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

还有就是用vector、stack、递归的~感觉没必要啊~