【题解】链表中倒数最后k个结点、删除链表的倒数第n个节点

链表中倒数最后k个结点

题目链接：链表中倒数最后k个结点

解题思路1：先找长度再找k对应的节点

首先遍历一遍链表找到链表的长度n
然后比较长度和k的大小关系，如果比k小，返回一个空节点
如果比k大，我们再从头节点遍历n-k次找到k对应的节点

代码如下：

1、可以用map，相对麻烦

    ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* cur = pHead;map<ListNode*, int> mp;int count = 0;while(cur != nullptr){mp[cur] = count;cur = cur->next;count++;}if(count < k) return nullptr;cur = pHead;while(cur != nullptr){if(mp[cur] == count-k){return cur;}cur = cur->next;}return nullptr;}

2、直接计算大小，方便简单

    ListNode* FindKthToTail(ListNode* pHead, int k) {int count = 0;ListNode* cur = pHead;while(cur != nullptr){count++;cur = cur->next;}if(count < k) return nullptr;cur = pHead;for(int i=0; i<count-k; i++){cur = cur->next;}return cur;}

解题思路2：快慢指针

代码如下：

    ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* fast = pHead;ListNode* slow = pHead;for(int i=0; i<k; i++){if(fast != nullptr){fast = fast->next;}else {return nullptr;}}while(fast != nullptr){fast = fast->next;slow = slow->next;}return slow;}

解题思路3：借助栈

栈只存放节点，并不改变节点的指向

代码如下：

    ListNode* FindKthToTail(ListNode* pHead, int k) {stack<ListNode*> st;ListNode* cur = pHead;while(cur != nullptr){st.push(cur);cur = cur->next;}if(st.size()==0 || st.size()<k) return nullptr;for(int i=0; i<k; i++){cur = st.top();st.pop();}return cur;}

删除链表的倒数第n个节点

题目链接：删除链表的倒数第n个节点

解题思路1：快慢指针

用两个指针来控制慢指针走到最后的时候是倒数第n个节点
首先先定义一个虚拟头结点，将所有节点统一管理，不再单独处理删除的头结点的情况
其次让快指针先走n步
接着让慢指针指向头节点，代表当前元素，pre指针指向添加的表头，这样两个快慢指针之间的距离一直是n
快慢指针同时移动，当快指针到达链表尾部也就是nullptr的时候，慢指针此时距nullptr有n个位置，也就是倒数第n个元素的位置
最后将pre节点的next指向慢指针的next删除这个节点，再接着返回虚拟头节点的next节点

代码如下：

    ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* res = new ListNode(0);res->next = head;ListNode* pre = res;ListNode* cur = head;ListNode* fast = head;//快指针先走n步while(n-- > 0){fast = fast->next;}//快慢指针一起走while(fast != nullptr){fast = fast->next;pre = cur;cur = cur->next;}pre->next = cur->next;return res->next;}

解题思路2：先找长度再找k对应的节点，再删除它

代码如下：

    ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* res = new ListNode(0);res->next = head;ListNode* pre = res;ListNode* cur = head;int count = 0;while(cur != nullptr){cur = cur->next;count++;}cur = head;for(int i=0; i<count-n; ++i){pre = cur;cur = cur->next;}pre->next = cur->next;return res->next;}