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

本文主要是介绍力扣 - 剑指 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. 删除链表的节点的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！