力扣 - 剑指 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)\)，指针占用常数大小额外空间