刷题——链表中倒数最后k个结点
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤𝑛≤1050≤n≤105，0≤𝑎𝑖≤1090≤ai≤109，0≤𝑘≤1090≤k≤109
要求：空间复杂度 𝑂(𝑛)O(n)，时间复杂度 𝑂(𝑛)O(n)
进阶：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)
示例1
输入：{1,2,3,4,5},2
复制返回值：{4,5}
示例2
输入：{2},8
复制返回值：{}
方法一：入栈出栈
class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereif(pHead == NULL || k == 0) return NULL;stack<ListNode*> stack;while(pHead != NULL){stack.push(pHead);//不断入栈pHead = pHead->next;}if(stack.size() < k) return NULL;ListNode *firstNode = NULL;while(--k >= 0){firstNode = stack.top();stack.pop();}return firstNode;}
};方法二：快慢指针法，fast先走k，slow后跟，之间距离+1，就是要得到的倒数k
ListNode* FindKthToTail(ListNode* pHead, int k) {// write code hereListNode* fast = pHead;ListNode* slow = pHead;//快指针先行k步for(int i=0; i<k;i++){if(fast != NULL) fast = fast->next;else slow = NULL;}while(fast != NULL){fast = fast->next;slow = slow->next;}return slow;}