脚本宝典收集整理的这篇文章主要介绍了力扣 - 剑指 Offer 18. 删除链表的节点，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

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

思路1（单指针）

• 首先判断是否删除的节点为第一个，是的话直接返回就行
• 如果删除的不是第一个，那么就遍历链表。每次遍历的时候我们都要判断一下下一个节点的值是否为要删除的节点的值：如果是的话，将当前节点指向待删除节点的下一个节点，这样子就成功删除了；否则就继续遍历

代码

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode p = head;

        // 例外情况，如果删除的是第一个节点，那就直接返回第一个节点
        if (p.val == val) {
            return head.next;
        }


        while (p.next != null) {
            if (p.next.val == val) {
                // 当前节点指向待删除节点的下一个节点，这样子就成功删除了
                p.next = p.next.next;
                return head;
            }
            p = p.next;
        }

        return head;
    }
}

复杂度分析

• 时间复杂度：(O(N))
• 空间复杂度：(O(1))，指针占用常数大小额外空间

思路2（双指针）

• 也是要先判断第一个节点是否为待删除的节点
• 然后我们使用两个指针，一个pre记录上一个节点，一个cur记录当前节点，等我们找到了待删除的节点，即cur.val == val，那就将pre的next指向cur的next

代码

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode pre = head;
        ListNode cur = head.next;

        // 也要判断第一个节点是否为要删除的节点
        if (head.val == val) {
            return head.next;
        }

        while (cur != null) {
            if (cur.val == val) {
                // 如果当前节点是待删除的节点，那就将 pre的next 指向 cur的next
                pre.next = cur.next;
                return head;
            }
            pre = cur;
            cur = cur.next;
        }

        return head;
    }
}

复杂度分析

• 时间复杂度：(O(N))
• 空间复杂度：(O(1))，指针占用常数大小额外空间

脚本宝典总结

以上是脚本宝典为你收集整理的力扣 - 剑指 Offer 18. 删除链表的节点全部内容，希望文章能够帮你解决力扣 - 剑指 Offer 18. 删除链表的节点所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。