LCOF18

[underwindfall]

• https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

• 思路

  • 哨兵节点
  • pre, curr指针

• [x] 刷15mins

• [x] 刷5mins

 // 哨兵节点
    // time O(n)
    // space O(1)
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        ListNode next = curr.next;
        while (curr != null) {
            if (curr.val == val) {
                prev.next = next;
            }

            prev = curr;
            curr = next;
            if (curr != null) {
                next = curr.next;
            }
        }
        return dummy.next;
    }

    // time O(n)
    // soace O(1)
    public ListNode deleteNodeBetter(ListNode head, int val) {
        if (head.val == val)
            return head.next;
        ListNode pre = head, cur = head.next;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if (cur != null)
            pre.next = cur.next;
        return head;
    }