18 删除链表的节点

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

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

解题思路：

遍历链表，当碰到节点 $node$ 满足 $node.val = val$ 时，将 $node$ 的前驱节点的 $next$ 指针指向 $node$ 的后去节点，$pre.next= node.next$ 。

代码：

public ListNode deleteNode(ListNode head, int val) {
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    while (head != null) {
        if (head.val == val) {
            pre.next = head.next;
            break;
        }
        pre = head;
        head = head.next;
    }
    return dummy.next;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为链表的节点数。最坏情况下，删除的节点在尾部，则需要遍历所有的节点。
• 空间复杂度$O(1)$：$dummy$ 占用常数大小的额外空间。