题目描述

请编写一个函数，删除单链表中的一个节点（除了尾节点）。函数传入的参数是需要删除的节点的指针。

注意：

• 链表中至少包含两个节点；
• 所有节点的值互不相同；
• 给定的节点一定不是尾节点，且一定合法；
• 函数不需要返回任何值；

给定一个数组 head = [4, 5, 1, 9]，表示如下链表：

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.

算法

(链表操作) $O(1)$

由于是单链表，我们不能找到前驱节点，所以我们不能按常规方法将该节点删除。
我们可以换一种思路，将下一个节点的值复制到当前节点，然后将下一个节点删除即可。

时间复杂度分析：只有常数次操作，所以时间复杂度是 $O(1)$。

C++ 代码

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