AcWing 33. 链表中倒数第k个节点

1. 先走k步（思路来自王道真题）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        ListNode *first = pListHead;
        ListNode *last = pListHead;
        while(k--){
            if(!first) return NULL;
            first = first->next;
        }
        while(first){
            first = first->next;
            last = last->next;
        }
        return last;
    }
};

2. 容易想到的方法

class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int len = 0;
        ListNode *cur = pListHead;
        while(cur){
             len++;
             cur = cur->next;
        }
        if(k > len) return 0;
        for(int i = 1; i < len - k + 1; i ++){
            pListHead = pListHead->next;
        }
        // cout << pListHead->val;
        return pListHead;
    }
};