在线 建站单页面网站带后台,如何建设电影网站,wordpress启用cookies,设计公司网站首页显示题目链接#xff1a;https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
1. 题目介绍#xff08;18. 删除链表的节点#xff09; 给定单向链表的头指针和一个要删除的节点的值#xff0c;定义一个函数删除该节点。 返回删除后的链表的头节点。 注意…题目链接https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/
1. 题目介绍18. 删除链表的节点 给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。 返回删除后的链表的头节点。 注意此题对比原题有改动 【测试用例】 示例 1: 输入: head [4,5,1,9], val 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点那么在调用了你的函数之后该链表应变为 4 - 1 - 9. 示例 2: 输入: head [4,5,1,9], val 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点那么在调用了你的函数之后该链表应变为 4 - 5 - 9. 【条件约束】 说明 题目保证链表中节点的值互不相同若使用 C 或 C 语言你不需要 free 或 delete 被删除的节点 【相似题目】 【LeetCode】No.83. 删除排序链表中的重复元素 – Java Version【LeetCode】No.237. 删除链表中的节点 – Java Version 2. 题解
2.1 常规方法 – O(n)
时间复杂度O(n)空间复杂度O(1) 条件讨论 ①. 普通情况要删除的节点下一节点不为null这个时候我们可以用下一节点的内容覆盖到当前节点来实现节点删除②. 尾节点当删除的节点是尾节点时由于尾节点的下一节点指向的是null所以我们没办法使用像普通情况下的节点那样使用下一节点来覆盖掉当前节点因此需要特殊处理。处理方式相当于我们提前进行了判断让尾节点的前一节点的next指向null③. 仅存在头节点这种情况属于当前节点既没有前一节点也没有后一节点需要单独判断直接让头节点指向null即可 ChatGPT代码分析如下不得不说确实是科技改变生活懒人必备了
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public ListNode deleteNode(ListNode head, int val) {// 判空if (head null) return null;// 定义变量cur用来指向当前节点ListNode cur head;// 删除头节点的情况即链表中只存在头节点且删除值与头节点相同if (head.next null head.val val) head null;while (cur.next ! null){// 普通情况采用下一节点覆盖当前节点的方法// 复制当前节点的下一个节点到当前节点并删除下一个节点ListNode pNext cur.next;if (cur.val val){cur.val pNext.val;cur.next pNext.next;pNext null;break;}cur cur.next;// 删除尾节点if (cur.next.next null cur.next.val val) {cur.next null;break;}}return head;}
}2.2 双指针 – O(n)
时间复杂度O(n)空间复杂度O(1) 思路 设节点 cur 的前驱节点为 pre 后继节点为 cur.next 则执行 pre.next cur.next 即可实现删除 cur 节点也属于常规做法即自己定义前驱节点然后通过将前驱节点的next指向当前节点的next从而实现对节点的删除。 class Solution {public ListNode deleteNode(ListNode head, int val) {if(head.val val) return head.next;ListNode pre head, cur head.next;while(cur ! null cur.val ! val) {pre cur;cur cur.next;}if(cur ! null) pre.next cur.next;return head;}
}3. 参考资料
[1] 面试题18. 删除链表的节点双指针清晰图解-- 双指针解法来源
