链表(Linked List)

动态数组有个明显的缺点，可能会造成内存空间浪费。 链表可以做到用多少就申请多少内存。

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。

237. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 – head = [4,5,1,9]，它可以表示为:

示例 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.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

删除一个链表中的节点， 最常见的方式是拿到前一个节点prev， 把prev的next指针指向当前元素node的下一个元素。

此题中，我们拿不到prev，所以把node的val替换为next的val， 并把node的next指向，node.next.next;

代码如下

1
2
3
4

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

时间复杂度 : O(1)

空间复杂度 : O(1)