剑指 Offer 面试题 18. 删除链表的节点

亦凉 2023-02-26 02:28 22阅读 0赞

点击上方“**图解面试算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

大家好，我是程序员吴师兄。

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 **面试题18. 删除链表的节点**，又是一道简简单单的送分题，基本上看一遍都能掌握。

题目链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

### 一、题目描述 ###

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

**注意**：此题对比原题有改动

**示例 1:**

输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

**示例 2:**

输入: head = [4,5,1,9], val = 1
    输出: [4,5,9]
    解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

**说明：**

*  题目保证链表中节点的值互不相同
 *  若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

### 二、题目解析 ###

这道题目可能会出错的地方是出现一个特殊的情况：**删除的节点是头节点**，这种情况下直接返回 `head.next` 即可。

具体思路可以看 **动画描述** 与 **参考代码** 。

### 三、动画描述 ###

### 四、图片描述 ###

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

### 五、参考代码    ###

class Solution {
        public ListNode deleteNode(ListNode head, int val) {
            //特殊情况处理，删除的节点是头结点时，比较特别
            if(head.val == val) return head.next;
            ListNode pre = head, cur = head.next;
            //当 cur 为空 或 cur 节点值等于 val 时跳出跳出循环
            while(cur != null && cur.val != val) {
                pre = cur;
                cur = cur.next;
            }
            //相当于覆盖掉了 val
            pre.next = cur.next;
            return head;
        }
    }

### 六、复杂度分析 ###

#### 时间复杂度 ####

时间复杂度 O(N)。

#### 空间复杂度 ####

空间复杂度 O(1)。

### 七、相关标签 ###

*  链表

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20230209/e47b618862334346a554b02045fa8f6e.png
[format_png 1]: /images/20230209/7df222680eb445b7830ec9060ae4df18.png
[format_png 2]: /images/20230209/4e6af843ca9f4234b9b3faae4e029f4d.png
[format_png 3]: /images/20230209/27e73a37b49a49c687c85fa78b9f821b.png
[format_png 4]: /images/20230209/bc6e9452ef544f51a9e62757751f9c8a.png
[format_png 5]: /images/20230209/c8e89d01e9b0427792581dd248445b8e.png
[format_png 6]: /images/20230209/b96215cce5984720893f333562a783ea.png
[format_png 7]: /images/20230209/c1c4460f0a054d1b890ca1a18625e841.png
[format_png 8]: /images/20230209/c89d52aaff16464b924ea9cc36878ee7.png
[format_png 9]: /images/20230209/f0ddb3fbc4d9419e9ec0e811deea5c25.png
[format_png 10]: /images/20230209/ea716c88686f42c7ba05ab4bdf8adfad.png