西安大型网站开发,网站建设与管理期末考试,福州seo经理招聘,如何做微信ppt模板下载网站文章目录 链表中倒数最后k个结点删除链表的倒数第n个节点 链表中倒数最后k个结点
题目链接#xff1a;链表中倒数最后k个结点
解题思路1#xff1a;先找长度再找k对应的节点
首先遍历一遍链表找到链表的长度n 然后比较长度和k的大小关系#xff0c;如果比k小#xff0c;… 文章目录 链表中倒数最后k个结点删除链表的倒数第n个节点 链表中倒数最后k个结点
题目链接链表中倒数最后k个结点
解题思路1先找长度再找k对应的节点
首先遍历一遍链表找到链表的长度n 然后比较长度和k的大小关系如果比k小返回一个空节点 如果比k大我们再从头节点遍历n-k次找到k对应的节点
代码如下
1、可以用map相对麻烦 ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* cur pHead;mapListNode*, 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 i0; icount-k; i){cur cur-next;}return cur;}解题思路2快慢指针
代码如下 ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* fast pHead;ListNode* slow pHead;for(int i0; ik; 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) {stackListNode* st;ListNode* cur pHead;while(cur ! nullptr){st.push(cur);cur cur-next;}if(st.size()0 || st.size()k) return nullptr;for(int i0; ik; 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 i0; icount-n; i){pre cur;cur cur-next;}pre-next cur-next;return res-next;}
