快乐的LeetCode --- 237. 删除链表中的节点

梦里梦外; 2023-07-24 09:19 18阅读 0赞

**题目描述：**

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

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

![在这里插入图片描述][20200410212827350.png_pic_center]  
**示例 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.

--------------------

**解题思路:**

从链表里删除一个节点 node 的最常见方法是修改之前节点的 next 指针，使其指向之后的节点。  
![在这里插入图片描述][20200410213020533.png_pic_center]  
由于我们无法访问想要删除的节点 之前 的节点，也不能修改该节点的 next 指针。因此，我们必须将想要删除的节点的值替换为它后面节点中的值，然后删除它之后的节点（之后的节点：在这里表示的是第二个‘4’后面的一条线）。

![在这里插入图片描述][20200410213106637.png_pic_center]  
![在这里插入图片描述][20200410213127106.png_pic_center]  
![在这里插入图片描述][20200410213141244.png_pic_center]  
因为我们知道要删除的节点不是列表的末尾，所以我们可以保证这种方法是可行的。

--------------------

**代码：**

class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
    
    class Solution(object):
        def deleteNode(self, node):
            node.val = node.next.val    # 将下一节点的值给当前要删除的节点
            node.next = node.next.next  # 把下一个节点干掉就OK了

--------------------

**C++写法：**

将下一个节点伪装成当前节点，然后将下一个节点干掉。  
![在这里插入图片描述][20200618100629691.png]

class Solution {
        
    public:
        void deleteNode(ListNode* node) {
        
            node -> val = node -> next -> val;
            node -> next = node -> next -> next;
        }
    };

简写

/**
     * 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) = *(node->next);
        }
    };

--------------------

**参考链接:**

[力扣][Link 1]

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/delete-node-in-a-linked-list][https_leetcode-cn.com_problems_delete-node-in-a-linked-list]

**同类题目：**

[面试题18. 删除链表的节点][18.]

[20200410212827350.png_pic_center]: /images/20230528/c0bc8c0e07b94bd38605d22459b83e3e.png
[20200410213020533.png_pic_center]: /images/20230528/086b8aed3b0f49ac893c9cb9508a632c.png
[20200410213106637.png_pic_center]: /images/20230528/ab5d3d20295a44d197f917465664009f.png
[20200410213127106.png_pic_center]: /images/20230528/ef8b3ff9065f49cbb6421c96474dabce.png
[20200410213141244.png_pic_center]: /images/20230528/d6ed02e7c3e747ff8394893ad572352b.png
[20200618100629691.png]: /images/20230528/533d8a65f8d44799889074aa1a2a5214.png
[Link 1]: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/solution/shan-chu-lian-biao-zhong-de-jie-dian-by-leetcode/
[https_leetcode-cn.com_problems_delete-node-in-a-linked-list]: https://leetcode-cn.com/problems/delete-node-in-a-linked-list
[18.]: https://blog.csdn.net/weixin_43283397/article/details/105438866