237.删除链表中的节点
237.1 题目
有一个单链表的 head，我们想删除其中的一个节点 node。
给你一个需要删除的节点 node。你将无法访问第一个节点 head。
链表的所有值都是唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
node前面的所有值顺序相同。node后面的所有值顺序相同。
自定义测试：
对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。我们将构建链表，并将节点传递给你的函数。输出将是调用你函数后的整个链表。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9。
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9。
提示：
- 链表中节点的数目范围是
[2, 1000] -1000 <= Node.val <= 1000- 链表中每个节点的值都是唯一的
- 需要删除的节点
node是链表中的节点，且不是末尾节点
237.2 题解
方法一：替换值删除节点
思路
这道题的特殊之处：只给你要删除的节点，不给你头节点。
所以无法找到前驱节点，也就不能用常规方法删除。
解决方法：用下一个节点的值覆盖当前节点，然后删除下一个节点。
相当于”借尸还魂”——当前节点”变成”了下一个节点，然后删除下一个节点。
举个例子：删除节点5
原链表：4 → 5 → 1 → 9
把5的值改成1：4 → 1 → 1 → 9
跳过第二个1：4 → 1 → 9
复杂度分析
- 时间复杂度：
O(1) - 空间复杂度：
O(1)
代码
// 方法一：替换值删除节点
static void DeleteNode1(ListNode node)
{
// 将当前节点的值替换为下一个节点的值
node.val = node.next.val;
// 跳过下一个节点，相当于删除了当前节点
node.next = node.next.next;
}
方法二：遍历删除节点
从当前节点开始，依次将后继节点的值复制到当前节点，直到倒数第二个节点。最后将倒数第二个节点的 next 置空，完成删除。
复杂度分析：
- 时间复杂度：
O(n)，需要遍历到链表末尾。 - 空间复杂度：
O(1)，无额外空间。
// 方法二：遍历删除节点
static void DeleteNode2(ListNode node)
{
// 将当前节点赋值给变量 current
ListNode current = node;
// 循环直到倒数第二个节点
while (current.next.next != null)
{
// 将当前节点的值替换为下一个节点的值
current.val = current.next.val;
// 移动到下一个节点
current = current.next;
}
// 删除最后一个节点，将当前节点的值替换为下一个节点的值
current.val = current.next.val;
// 将当前节点的 next 指针置为 null，删除最后一个节点
current.next = null;
}
237.3 代码
using System;
using System.Collections.Generic;
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
class Program
{
static void Main()
{
#region 题目
// 有一个单链表的 head，我们想删除它其中的一个节点 node。
// 给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
// 链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
// 删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
// 1. 给定节点的值不应该存在于链表中。
// 2. 链表中的节点数应该减少 1。
// 3. node 前面的所有值顺序相同。
// 4. node 后面的所有值顺序相同。
#endregion
#region 测试
// 示例 1
ListNode head1 = BuildLinkedList(new int[] { 4, 5, 1, 9 });
ListNode node1 = FindNode(head1, 5);
DeleteNode1(node1);
PrintLinkedList(head1);
// 示例 2
ListNode head2 = BuildLinkedList(new int[] { 4, 5, 1, 9 });
ListNode node2 = FindNode(head2, 1);
DeleteNode2(node2);
PrintLinkedList(head2);
#endregion
}
#region 答案
// 方法一：替换值删除节点
static void DeleteNode1(ListNode node)
{
// 将当前节点的值替换为下一个节点的值
node.val = node.next.val;
// 跳过下一个节点，相当于删除了当前节点
node.next = node.next.next;
}
// 方法二：遍历删除节点
static void DeleteNode2(ListNode node)
{
// 将当前节点赋值给变量 current
ListNode current = node;
// 循环直到倒数第二个节点
while (current.next.next != null)
{
// 将当前节点的值替换为下一个节点的值
current.val = current.next.val;
// 移动到下一个节点
current = current.next;
}
// 删除最后一个节点，将当前节点的值替换为下一个节点的值
current.val = current.next.val;
// 将当前节点的 next 指针置为 null，删除最后一个节点
current.next = null;
}
#endregion
#region 辅助方法
// 构建链表
static ListNode BuildLinkedList(int[] values)
{
ListNode dummy = new ListNode();
ListNode current = dummy;
foreach (int val in values)
{
current.next = new ListNode(val);
current = current.next;
}
return dummy.next;
}
// 查找节点
static ListNode FindNode(ListNode head, int target)
{
ListNode current = head;
while (current != null)
{
if (current.val == target)
{
return current;
}
current = current.next;
}
return null;
}
// 打印链表
static void PrintLinkedList(ListNode head)
{
ListNode current = head;
while (current != null)
{
Console.Write($"{current.val} -> ");
current = current.next;
}
Console.WriteLine("null");
}
#endregion
}
237.4 运行结果
4 -> 1 -> 9 -> null
4 -> 5 -> 9 -> null
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
