企业网站 wordpress,wordpress留言代码,html制作一个个人主页网站,安卓优化大师官方下载力扣网 19 删除链表的倒数第N个结点
题目描述
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a;
输入#xff1a;head …力扣网 19 删除链表的倒数第N个结点
题目描述
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
示例 1 输入head [1,2,3,4,5], n 2
输出[1,2,3,5]示例 2
输入head [1], n 1
输出[]示例 3
输入head [1,2], n 1
输出[1]提示
链表中结点的数目为 sz1 sz 300 Node.val 1001 n sz 思路分析
关于这道题有两种思路和三种不同的方法我们来一一分析。 思路1快慢指针法
我们之前做过一题找出链表的倒数第N个结点我们可以在此基础上进行找到第N个结点然后删除即可但这里涉及到一些特殊情况
1.当链表长度只有一个且n1时如果直接释放头结点的话会野指针
2.当需要删除的结点是头结点直接删除的话会丢失后面的结点。
这里分成两种方法进行实现
1.带一个哨兵位
我们发现往往与删除功能有关的题都会需要考虑链表为空的情况但只要定义一个哨兵位指向头结点就能很好解决减少代码量提供效率。
有了哨兵位删除也方便了许多。我们通过快慢指针法遍历链表得到slow指向的结点就是需要删除的结点但此时还得需要获得它的前驱结点这时就得定义第三个指针在遍历的时候指向它的前驱结点且又得考虑链表为空的情况在方法2不带哨兵位会进行解释但如果有了哨兵位我们可以让快指针从头结点开始二慢指针从哨兵位开始遍历结束后slow指针的下一个就是要删除的结点相当于不找删除结点而是找删除结点的前驱结点直接指向下一个结点的下一个完成删除。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位不存储有效数据用来解决链表为空的情况dummy-val0;dummy-nexthead;struct ListNode* fasthead;//快指针struct ListNode* slowdummy;//慢指针while(n--){if(fastNULL){return NULL;}fastfast-next;}while(fast){fastfast-next;slowslow-next;}slow-nextslow-next-next;struct ListNode* ansdummy-next;free(dummy);//动态开辟的空间记得释放return ans;}
2.不带哨兵位
有些小伙想要锻炼自己的代码能力一般是不喜欢用哨兵位貌似有点投机取巧的感觉作者本人是这么想的。。。下面我们来介绍一下不带哨兵位的做法。
既然不带哨兵位我们就需要第三个指针在遍历时保存删除结点的前驱结点同时链表为空和头结点为野指针的情况要逐一考虑。
当我们需要删除的结点是头结点就需要将head指针移动到下一个当作新的头结点再将原来的结点释放。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* fasthead;struct ListNode* slowhead;struct ListNode* prevhead;while(n--){if(fastNULL){return NULL;}fastfast-next;}while(fast){prevslow;slowslow-next;fastfast-next;}if(slowhead){headslow-next;free(slow);}else{prev-nextslow-next;free(slow);}return head;} 思路2链栈
这是力扣官方的一个解题思路只需要遍历一次即可。
步骤就是将链表的所有元素入栈根据n的值来决定出栈的次数出栈完后会发现此时栈顶元素就是需要删除结点的前驱结点之后进行删除。
链表入栈的方式和链表的头插是类似的为了增加效率我们带一个哨兵位嘻嘻。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct Stack//链栈类{struct ListNode* val;//存储的元素类型是链表struct Stack* next;//指向下一个栈类};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位初始化dummy-val0;dummy-nexthead;struct ListNode* curdummy;struct Stack* stkNULL;while(cur)//入栈{struct Stack* tmp(struct Stack*)malloc(sizeof(struct Stack));//基于头插法实现tmp-valcur;tmp-nextstk;stktmp;curcur-next;}while(n--)//出栈{struct Stack* tmpstk-next;free(stk);stktmp;}struct ListNode* prevstk-val;//栈顶元素就是删除元素的前驱结点prev-nextprev-next-next;//进行删除struct ListNode* ansdummy-next;//释放开辟的哨兵位free(dummy);return ans;}
