【LeetCode】剑指 Offer 18. 删除链表的节点（题目一） p119 -- Java Version

题目链接：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. 删除链表的节点（双指针，清晰图解）-- 双指针解法来源