题解 | #链表中倒数最后k个结点#
链表中倒数最后k个结点
https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include <stack> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* FindKthToTail(ListNode* pHead, int k) { // write code here // 这道题榜单前几用vector做的话无论是运行时间还是占用内存都是占有优势的,是不是vector就是比stack好呢? // 在榜单前几看到有人用双指针做,不得不说真是佩服! // 将指针从头到尾,然后从尾到k的这个过程看成是环结构,然后使用双指针,真是脑洞大开! // 还有形成-k和+k对称结构的链表,父指针带着子指针移动的双指针结构,牛! stack<ListNode*> s; ListNode* node=pHead; if (node==nullptr) { return nullptr; } while (node!=nullptr) { // ListNode* pnext=node->next; s.push(node); // node=pnext; node=node->next; } if (s.size()<k) { return nullptr; } if (k==0) { return nullptr; } for (int i=0; i<k-1; ++i) { s.pop(); } return s.top(); } };