网站建设开源程序,网站建设ui设计,吴江区桃源镇做网站,wordpress调用图标icon目录 题目
解法一
双指针算法
核心思想
执行流程
具体例子
代码
解法二
两次遍历法
核心思想
执行流程
具体例子
代码 题目
19. 删除链表的倒数第 N 个结点 - 力扣#xff08;LeetCode#xff09;
解法一
双指针算法
核心思想
利用双指针间隔固定距离(n1)LeetCode
解法一
双指针算法
核心思想
利用双指针间隔固定距离(n1)当快指针到达链表末尾时慢指针恰好位于倒数第n个节点的前一位置。
执行流程
创建哑节点dummy指向链表头部初始化快指针fast和慢指针slow都指向dummyfast先前进n1步fast和slow同时前进直到fast到达NULLslow此时指向待删除节点的前一节点执行删除操作返回dummy-next作为新的头节点
具体例子
对于链表1→2→3→4→5删除倒数第2个节点(n2)
创建dummy→1→2→3→4→5fast和slow初始都指向dummyfast前进3步(n1)fast指向3fast和slow同时前进当fast到达5后的NULLslow指向3删除slow-next(即4)3→5返回dummy-next1→2→3→5
代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0);dummy-next head;ListNode* fast dummy;ListNode* slow dummy;for(int i 0; in1; i){if(!fast){return head;}fast fast-next;}while(fast){fast fast-next;slow slow-next;}if(slow-next){ListNode* toDelete slow-next;slow-next slow-next-next;delete toDelete;}ListNode* newhead dummy-next;delete dummy;return newhead;}
};
解法二
两次遍历法
核心思想
执行流程
创建哑节点dummy指向链表头部第一次遍历计算链表长度length计算待删除节点的正序位置position length - n第二次遍历前进position步找到待删除节点的前驱删除目标节点返回dummy-next作为新的头节点
具体例子
对于链表1→2→3→4→5删除倒数第2个节点(n2)
创建dummy→1→2→3→4→5计算链表长度length 5找到正序位置position 5 - 2 3从dummy开始前进3步到达节点3删除节点3的下一个节点(4)3→5返回dummy-next1→2→3→5
双指针法效率更高因为只需一次遍历两次遍历法思路更直观易于理解。
代码
ListNode* removeNthFromEnd(ListNode* head, int n) {// 创建哑节点ListNode* dummy new ListNode(0);dummy-next head;// 第一次遍历计算链表长度int length 0;ListNode* first head;while (first) {length;first first-next;}// 计算要删除节点的位置int position length - n;// 找到待删除节点的前一个节点ListNode* curr dummy;for (int i 0; i position; i) {curr curr-next;}// 删除节点并释放内存ListNode* toDelete curr-next;curr-next curr-next-next;delete toDelete;// 获取新的头节点head dummy-next;delete dummy;return head;
}
