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

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

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

题目难度：简单
方法一

链接：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 的节点分需为两步：定位节点、修改引用。

定位节点：遍历链表，直到 head.val == val 时跳出，即可定位目标节点。
修改引用：设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。

算法流程：

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