删除中间节点

难度:

标签:

题目描述

Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

Example:

Input: the node c from the linked list a->b->c->d->e->f
Output: nothing is returned, but the new linked list looks like a->b->d->e->f

代码结果

运行时间: 48 ms, 内存: 14.8 MB

/*
 * 思路：
 * 1. 虽然 Java Stream 主要用于处理集合，但我们依然可以用这种方式处理链表。
 * 2. 将链表转换为一个可变的 ArrayList。
 * 3. 通过 Stream 操作修改列表，然后更新链表结构。
 */
import java.util.*;
import java.util.stream.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public void deleteNode(ListNode node) {
        if (node == null || node.next == null) return;
        ListNode current = node;
        while (current.next != null) {
            current.val = current.next.val;
            if (current.next.next == null) {
                current.next = null;
            } else {
                current = current.next;
            }
        }
    }
}

解释

方法:

该题解的核心思路是通过复制节点的方式实现删除操作。具体做法是将待删除节点的下一个节点的值复制到当前节点，然后将当前节点的next指针指向下下个节点，这样就相当于删除了原节点的下一个节点，间接达到了删除当前节点的效果。由于直接修改了链表结构，因此无需返回任何值。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆

在这种删除中间节点的方法中，如果待删除节点是链表中的倒数第二个节点，它的`next.next`是什么？这种情况下如何处理？

▷

如果待删除节点是链表中的倒数第二个节点，其`next.next`将是`None`，因为`next`指向的是最后一个节点，而最后一个节点的`next`是`None`。在这种情况下，可以正常复制倒数第一个节点的值到倒数第二个节点，并将倒数第二个节点的`next`设置为`None`，从而删除倒数第一个节点。

🦆

该算法是否考虑了待删除节点为链表尾节点的情况？如果是尾节点，如何应对因`node.next`为`None`而无法复制值的问题？

▷

该算法并没有直接考虑待删除节点为链表尾节点的情况。由于算法依赖于节点后续的存在（至少需要一个后续节点来复制其值），因此如果`node.next`为`None`（即节点为尾节点），则无法执行此删除方法。这种方法仅适用于非尾部节点。

🦆

为什么这种删除方法不需要考虑链表的头节点？请解释其逻辑。

▷

这种删除方法假设待删除的节点不是头节点，因为它依赖于节点的前驱节点（即至少存在一个节点在待删除节点之前）。在这种方法中，没有直接访问或修改前驱节点，而是通过修改当前节点的值和指针来实现删除效果。因此，这种方法不适用于头节点，因为头节点没有前驱节点。

🦆

删除操作是否会影响到其他引用同一节点的数据结构或变量？如果有其他变量引用了被删除的节点，它们的状态会如何？

▷

删除操作通过修改值和指针来'伪删除'节点，实际上并没有从内存中移除节点。如果其他变量或数据结构引用了被删除的节点，它们将看到值被修改后的状态。例如，如果有一个变量引用了被'删除'的节点，那么该变量现在将引用一个值被改变且`next`指针被重定向的节点。这可能导致不一致和意外的行为，特别是在并发环境中。

删除中间节点

题目描述

代码结果

解释

代码细节讲解

相关问题