劍指Offer面試題：12.在O(1)時間刪除鏈表結點

題目：給定單向鏈表的頭指針和一個結點指針，定義一個函數在O(1)時間刪除該結點。在單向鏈表中刪除一個結點，最常規的做法無疑是從鏈表的頭結點開始，順序遍歷查找要刪除的結點，并在鏈表中刪除該結點。這種思路由于需要順序查找，時間復雜度自然就是O(n)。是不是一定需要得到被刪除的結點的前一個結點呢？答案是否定的。

一、題目：在O(1)時間刪除鏈表結點

題目：給定單向鏈表的頭指針和一個結點指針，定義一個函數在O(1)時間刪除該結點。

　　原文采用的是C/C++，這里采用C#，節點定義如下：

    public class Node<T>
    {
        // 數據域
        public T Item { get; set; }
        // 指針域
        public Node<T> Next { get; set; }

        public Node()
        {
        }

        public Node(T item)
        {
            this.Item = item;
        }
    }

　　要實現的DeleteNode方法定義如下：

    public static void DeleteNode(Node<int> headNode, Node<int> deleteNode)
    {
    }

二、解題思路

2.1 常規思路

　　在單向鏈表中刪除一個結點，最常規的做法無疑是從鏈表的頭結點開始，順序遍歷查找要刪除的結點，并在鏈表中刪除該結點。這種思路由于需要順序查找，時間復雜度自然就是O(n)。

2.2 正確思路

　　是不是一定需要得到被刪除的結點的前一個結點呢？答案是否定的。

　　我們可以很方便地得到要刪除的結點的一下結點。因此，我們可以把下一個結點的內容復制到需要刪除的結點上覆蓋原有的內容，再把下一個結點刪除，就相當于把當前需要刪除的結點刪除了。

　　但是，還有兩個特殊情況需要進行考慮：

　　（1）如果要刪除的結點位于鏈表的尾部，那么它就沒有下一個結點：

　　此時我們仍然從鏈表的頭結點開始，順序遍歷得到該結點的前序結點，并完成刪除操作，這仍然屬于O(n)時間的操作。

　　（2）如果鏈表中只有一個結點，而我們又要刪除鏈表的頭結點（也是尾結點）：

　　此時我們在刪除結點之后，還需要把鏈表的頭結點設置為NULL。

　　最后，通過綜合最壞情況（尾節點需要順序查找，1次）和最好情況（n-1次），因此平均時間復雜度為：

　　需要注意的是：受到O(1)時間的限制，我們不得不把確保結點在鏈表中的責任推給了函數DeleteNode的調用者。

三、解決問題

3.1 代碼實現

    public static void DeleteNode(Node<int> headNode, Node<int> deleteNode)
    {
        if (headNode == null || deleteNode == null)
        {
            return;
        }

        if (deleteNode.Next != null) // 鏈表有多個節點，要刪除的不是尾節點:O(1)時間
        {
            Node<int> tempNode = deleteNode.Next;
            deleteNode.Item = tempNode.Item;
            deleteNode.Next = tempNode.Next;

            tempNode = null;
        }
        else if (headNode == deleteNode) // 鏈表只有一個結點，刪除頭結點（也是尾結點）:O(1)時間
        {
            deleteNode = null;
            headNode = null;
        }
        else // 鏈表有多個節點，要刪除的是尾節點:O(n)時間
        {
            Node<int> tempNode = headNode;
            while(tempNode.Next != deleteNode)
            {
                tempNode = tempNode.Next;
            }

            tempNode.Next = null;
            deleteNode = null;
        }
    }

3.2 單元測試

　　（1）封裝返回結果

　　該方法作為單元測試的對比方法，主要用來對比實際值與期望值是否一致：

    public static string GetPrintNodes(Node<int> headNode)
    {
        if (headNode == null)
        {
            return string.Empty;
        }

        StringBuilder sbNodes = new StringBuilder();
        while(headNode != null)
        {
            sbNodes.Append(headNode.Item);
            headNode = headNode.Next;
        }

        return sbNodes.ToString();
    }

View Code

　　（2）測試用例

    // 鏈表中有多個結點，刪除中間的結點
    [TestMethod]
    public void DeleteNodeTest1()
    {
        Node<int> head1 = new Node<int>(1);
        Node<int> head2 = new Node<int>(2);
        Node<int> head3 = new Node<int>(3);
        Node<int> head4 = new Node<int>(4);
        Node<int> head5 = new Node<int>(5);

        head1.Next = head2;
        head2.Next = head3;
        head3.Next = head4;
        head4.Next = head5;

        Program.DeleteNode(head1, head3);
        Assert.AreEqual(Program.GetPrintNodes(head1),"1245");
    }

    // 鏈表中有多個結點，刪除尾結點
    [TestMethod]
    public void DeleteNodeTest2()
    {
        Node<int> head1 = new Node<int>(1);
        Node<int> head2 = new Node<int>(2);
        Node<int> head3 = new Node<int>(3);
        Node<int> head4 = new Node<int>(4);
        Node<int> head5 = new Node<int>(5);

        head1.Next = head2;
        head2.Next = head3;
        head3.Next = head4;
        head4.Next = head5;

        Program.DeleteNode(head1, head5);
        Assert.AreEqual(Program.GetPrintNodes(head1), "1234");
    }

    // 鏈表中有多個結點，刪除頭結點
    [TestMethod]
    public void DeleteNodeTest3()
    {
        Node<int> head1 = new Node<int>(1);
        Node<int> head2 = new Node<int>(2);
        Node<int> head3 = new Node<int>(3);
        Node<int> head4 = new Node<int>(4);
        Node<int> head5 = new Node<int>(5);

        head1.Next = head2;
        head2.Next = head3;
        head3.Next = head4;
        head4.Next = head5;

        Program.DeleteNode(head1, head1);
        Assert.AreEqual(Program.GetPrintNodes(head1), "2345");
    }

    // 鏈表中只有一個結點，刪除頭結點
    [TestMethod]
    public void DeleteNodeTest4()
    {
        Node<int> head1 = new Node<int>(1);

        Program.DeleteNode(head1, head1);
        head1 = null;
        Assert.AreEqual(Program.GetPrintNodes(head1), "");
    }

    // 鏈表為空
    [TestMethod]
    public void DeleteNodeTest5()
    {
        Program.DeleteNode(null, null);
        Assert.AreEqual(Program.GetPrintNodes(null), "");
    }