18 删除链表的节点

Lin2J
2021-07-21 / 0 评论 / 73 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 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$ 占用常数大小的额外空间。