Leetcode 237：Delete Node in a Linked List

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

说人话：

单链表中结点不重复，给你一个结点，删除掉这个结点。

要点：

• 没有给头结点，只给了要删除的那个结点
• 结点不重复
• 链表至少包含两个节点
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点

示例：

[法1] 修改结点的值

思路

因为本题没有给我们 head 结点，所以我们不可能得到要删除的结点 node 的前一个结点 pre，所以是不可能删除掉 node 结点本身的。

我们可以利用结点唯一这个条件，将要删除的结点 node 后面的结点 next 的值覆盖到 node 上面，然后删除掉 next 直接，就等价于删除掉 node 结点。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;
    }
}

提交结果

代码分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)