在 O（1）時間刪除鏈表結(jié)點

http://wiki.jikexueyuan.com/project/for-offer/images/17.png" alt="" />

代碼實現(xiàn)：

[java] view plaincopyprint?
public class Test13 {  
    /** 
     * 鏈表結(jié)點 
     */  
    public static class ListNode {  
        int value; // 保存鏈表的值  
        ListNode next; // 下一個結(jié)點  
    }  
    /** 
     * 給定單向鏈表的頭指針和一個結(jié)點指針，定義一個函數(shù)在0(1)時間刪除該結(jié)點, 
     * 【注意1：這個方法和文本上的不一樣，書上的沒有返回值，這個因為JAVA引用傳遞的原因， 
     * 如果刪除的結(jié)點是頭結(jié)點，如果不采用返回值的方式，那么頭結(jié)點永遠(yuǎn)刪除不了】 
     * 【注意2：輸入的待刪除結(jié)點必須是待鏈表中的結(jié)點，否則會引起錯誤，這個條件由用戶進(jìn)行保證】 
     * 
     * @param head        鏈表表的頭 
     * @param toBeDeleted 待刪除的結(jié)點 
     * @return 刪除后的頭結(jié)點 
     */  
    public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) {  
        // 如果輸入?yún)?shù)有空值就返回表頭結(jié)點  
        if (head == null || toBeDeleted == null) {  
            return head;  
        }  
        // 如果刪除的是頭結(jié)點，直接返回頭結(jié)點的下一個結(jié)點  
        if (head == toBeDeleted) {  
            return head.next;  
        }  
          // 下面的情況鏈表至少有兩個結(jié)點  
        // 在多個節(jié)點的情況下，如果刪除的是最后一個元素  
        if (toBeDeleted.next == null) {  
            // 找待刪除元素的前驅(qū)  
            ListNode tmp = head;  
            while (tmp.next != toBeDeleted) {  
                tmp = tmp.next;  
            }  
            // 刪除待結(jié)點  
            tmp.next = null;  
        }  
        // 在多個節(jié)點的情況下，如果刪除的是某個中間結(jié)點  
        else {  
            // 將下一個結(jié)點的值輸入當(dāng)前待刪除的結(jié)點  
            toBeDeleted.value = toBeDeleted.next.value;  
            // 待刪除的結(jié)點的下一個指向原先待刪除引號的下下個結(jié)點，即將待刪除的下一個結(jié)點刪除  
            toBeDeleted.next = toBeDeleted.next.next;  
        }  
        // 返回刪除節(jié)點后的鏈表頭結(jié)點  
        return head;  
    }  
      /** 
     * 輸出鏈表的元素值 
     * 
     * @param head 鏈表的頭結(jié)點 
     */  
    public static void printList(ListNode head) {  
        while (head != null) {  
            System.out.print(head.value + "->");  
            head = head.next;  
        }  
        System.out.println("null");  
    }  
     public static void main(String[] args) {  
        ListNode head = new ListNode();  
        head.value = 1;  
        head.next = new ListNode();  
        head.next.value = 2;  
        head.next.next = new ListNode();  
        head.next.next.value = 3;  
        head.next.next.next = new ListNode();  
        head.next.next.next.value = 4;  
        ListNode middle = head.next.next.next.next = new ListNode();  
        head.next.next.next.next.value = 5;  
        head.next.next.next.next.next = new ListNode();  
        head.next.next.next.next.next.value = 6;  
        head.next.next.next.next.next.next = new ListNode();  
        head.next.next.next.next.next.next.value = 7;  
        head.next.next.next.next.next.next.next = new ListNode();  
        head.next.next.next.next.next.next.next.value = 8;  
        ListNode last = head.next.next.next.next.next.next.next.next = new ListNode();  
        head.next.next.next.next.next.next.next.next.value = 9;  
        head = deleteNode(head, null); // 刪除的結(jié)點為空  
        printList(head);  
        ListNode node = new ListNode();  
        node.value = 12;  
        head = deleteNode(head, head); // 刪除頭結(jié)點  
        printList(head);  
        head = deleteNode(head, last); // 刪除尾結(jié)點  
        printList(head);  
        head = deleteNode(head, middle); // 刪除中間結(jié)點  
        printList(head);  
        head = deleteNode(head, node); // 刪除的結(jié)點不在鏈表中  
        printList(head);  
    }  
}  

運行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/18.png" alt="" />