題目描述

給定單向鏈表的頭指針和一個(gè)節(jié)點(diǎn)指針，定義一個(gè)函數(shù)在O(1)時(shí)間內(nèi)刪除該節(jié)點(diǎn)。

解題思路:

1. 可以要?jiǎng)h除的節(jié)點(diǎn)A的下一個(gè)節(jié)點(diǎn)B的值復(fù)制到當(dāng)前節(jié)點(diǎn)，再刪除節(jié)點(diǎn)B，即可實(shí)現(xiàn)在O(1)時(shí)間內(nèi)刪除節(jié)點(diǎn)。
2. 如果要?jiǎng)h除的節(jié)點(diǎn)A就是頭節(jié)點(diǎn)，則將頭節(jié)點(diǎn)置為null即可。
3. 如果要?jiǎng)h除的節(jié)點(diǎn)A是最后一個(gè)節(jié)點(diǎn)，則仍然需要使用遍歷的方式。

代碼

ListNode deleteNode(ListNode head, ListNode nodeToBeDel) {
    if (head == null ) {
        return null;
    }
    if (nodeToBeDel == null) {
        return head;
    }
    if (nodeToBeDel.next != null) {
        // 被刪除的是中間節(jié)點(diǎn)
        nodeToBeDel.value = nodeToBeDel.next.value;
        nodeToBeDel.next = nodeToBeDel.next.next;
    } else if (head == nodeToBeDel) {
        // 被刪除的是頭節(jié)點(diǎn)
        head = null;
    }else {
        // 被刪除的是尾部節(jié)點(diǎn)
        ListNode node = head;
        while (node.next != nodeToBeDel) {
            node = node.next;
        }
        node.next = null;
    }
    return head;
}