首页 > 编程学习 > JZ18 删除链表的节点

JZ18 删除链表的节点

发布时间:2022/10/1 0:56:52

链表介绍:
链表是以节点的方式来存储,是链式存储
每个节点包含 data 域, next 域:指向下一个节点
链表的各个节点不一定是连续存储
链表分带头节点的链表和没有头节点的链表

题目:
给定单链表的一个头,删除该链表指定节点,该链表所有元素不同

题解:
链表删除元素,即是将它前一个元素本来指向它自己的指针指向它后一个元素,这样,没有指针指向它,它也不指向其他元素,即将自己从链表中摘了出来。对于不带头结点的链表,如果要删除第一个元素,还是给它加一个默认的头结点node比较容易操作。使用一个临时节点temp指向加了头结点后的链表,遍历寻找节点值与待删除值相等的节点,找到后断开连接即可。返回的时候返回node的下一个节点即可。

解法:

public ListNode deleteNode (ListNode head, int val) {
        ListNode node = new ListNode(Integer.MIN_VALUE);
        node.next = head;
        ListNode temp = node;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
        return node.next;
    }

复杂度分析:
时间复杂度:O(n),其中n为链表长度,最坏遍历整个链表
空间复杂度:O(1),常数级变量,没有使用额外的存储空间

总结:链表删除有四个关键点:
1).对于不带头结点的链表可以自己给它添加一个头节点。
2).遍历的时候使用一个临时节点,循环的出口为当前节点的下一个节点为null或者寻找到目标节点后调出循环。
3).找到目标节点后:temp.next = temp.next.next;
4).返回加了头节点的链表的下一个节点。

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号