【leetcode】剑指 Offer 18. 删除链表的节点

Myth丶恋晨 2022-11-15 11:59 155阅读 0赞

### 剑指 Offer 18. 删除链表的节点 ###

*  题目难度：简单
 *  方法一

> 链接：[https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/][https_leetcode-cn.com_problems_shan-chu-lian-biao-de-jie-dian-lcof]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：简单 #

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

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

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

限制：

题目保证链表中节点的值互不相同

模板

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

# 方法一 #

思路：

*  整体思路是使用双指针，前指针`pre` 和 当前指针`cur`，当前方指针遇到要删除的值时，则使用后方指针重新构造连接并跳过该值
    
     *  首先判断头指针是否为 null，如果为空则直接返回 null
     *  如果头指针 head.val 即为要删除的值，则直接返回 head.next 即可
     *  设节点 `cur` 的前驱节点为 `pre` 和后继节点 `cur.next`
     *  双指针一直遍历链表，直到遍历到链表结尾或等于要删除的值时则跳出循环
     *  如果找到要删除的值，则令 `pre.next = cur.next`，相当于将链表中的值删除

解题思路：

本题删除值为 `val` 的节点分需为两步：定位节点、修改引用。

1.  定位节点： 遍历链表，直到 `head.val == val` 时跳出，即可定位目标节点。
2.  修改引用： 设节点 `cur` 的前驱节点为 `pre` ，后继节点为 `cur.next` ；则执行 `pre.next = cur.next` ，即可实现删除 `cur` 节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

算法流程：

1.  **特例处理**： 当应删除头节点 `head` 时，直接返回 `head.next` 即可。
2.  **初始化**： `pre = head` , `cur = head.next` 。
3.  **定位节点**： 当 `cur` 为空 **或** `cur` 节点值等于 `val` 时跳出。
    
    1.  保存当前节点索引，即 `pre = cur` 。
    2.  遍历下一节点，即 `cur = cur.next` 。
4.  **删除节点**： 若 `cur` 指向某节点，则执行 `pre.next = cur.next` ；若 `cur` 指向  n u l l null null ，代表链表中不包含值为 `val` 的节点。
5.  **返回值**： 返回链表头部节点 `head` 即可。

复杂度分析：

*  时间复杂度  O ( N ) O(N) O(N)：  N N N 为链表长度，删除操作平均需循环  N / 2 N/2 N/2 次，最差  N N N 次。
 *  空间复杂度  O ( 1 ) O(1) O(1) ： `cur`, `pre` 占用常数大小额外空间。

class Solution {
        
        public ListNode deleteNode(ListNode head, int val) {
        
            if(head.val == val) return head.next;
            ListNode pre = head, cur = head.next;
            while(cur != null && cur.val != val) {
        
                pre = cur;
                cur = cur.next;
            }
            if(cur != null) pre.next = cur.next;
            return head;
        }
    }

class Solution {
        
        public ListNode deleteNode(ListNode head, int val) {
        
            //边界条件判断
            if (head == null) return head;
            //如果要删除的是头结点，直接返回头结点的下一个结点即可
            if (head.val == val) return head.next;
            
            ListNode cur = head;
            //找到要删除结点的上一个结点
            while (cur.next != null && cur.next.val != val) {
        
                cur = cur.next;
            }
            //删除该结点
            if(cur.next != null) 
            	cur.next = cur.next.next;
            return head;
        }
    }

[https_leetcode-cn.com_problems_shan-chu-lian-biao-de-jie-dian-lcof]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221022/2b8130dd1345409088036f5199398b87.png