在O(1)的時間内删除結點劍指Offer_13: 在 O(1) O ( 1 ) O(1)的時間内删除結點

劍指Offer_13: 在 O(1) O ( 1 ) 的時間内删除結點

2018/05/14 星期一

題目: 給定單項連結清單的頭指針和一個結點指針，定義一個函數在 O(1)​ O ( 1 ) ​ 的時間删除該結點。連結清單結點和函數的定義如下：

class ListNode {
    int data;
    ListNode nextNode;
}
public void deleteNode(ListNode head, ListNode deListNode)
           

思考三分鐘。。。。

在單連結清單中删除一個結點，最簡單的方法無疑就是從連結清單的頭結點開始，順序周遊查找要删除的結點，并在連結清單中删除該結點。

• 上圖(a)中表示一個單連結清單
• 上圖(b)中，表示順序周遊删除i結點。删除i結點之前，先從頭結點開始周遊到i前面的一個結點h，然後把h結點的指針指向i的下一個節點j，再删除節點i(正常思路複雜度 O(n) O ( n ) )。
• 上圖(c)中，把結點j中的内容複制到結點i中，再把i中的指針指向節點j的指針。這種方法不用周遊i結點前面的元素。時間複雜度為 O(1) O ( 1 )

基于圖(c)的思路中還需要考慮一個問題，如果更新的節點位于連結清單的尾部(尾結點)，怎麼辦，它沒有下一個節點？這時候隻能通過順序周遊查找（圖（b）中表示的方法）。如果我們有一個節點，删除的位置即是頭結點也是尾結點，當我們在删除的時候除了删除節點還是将頭結點置為null。完整代碼如下：

public void deleteNode(ListNode head, ListNode deListNode) {
    if (deListNode == null || head == null) {
        return;
    }
    // 如果删除頭結點
    if (head == deListNode) {
        head = null;
    } else {
        // 如果删除結點為尾結點
        if (deListNode.nextNode == null) {
            ListNode pointListNode = head;
            while (pointListNode.nextNode.nextNode != null) {
                pointListNode = pointListNode.nextNode;
            }
            pointListNode.nextNode = null;
        } else {
            deListNode.data = deListNode.nextNode.data;
            deListNode.nextNode = deListNode.nextNode.nextNode;
        }
    }
}
           

算法的時間複雜度：對于n-1個非尾結點而言，我們是可以在 O(1) O ( 1 ) 的時間内完成操作；對于尾結點我們仍然需要順序查找，時間複雜度為 O(n) O ( n ) 。總的平均時間複雜度是 [(n−1)∗O(1)+O(n)]n [ ( n − 1 ) ∗ O ( 1 ) + O ( n ) ] n ，結果還是 O(1) O ( 1 ) 。

上述的代碼并不是完美的代碼，它基于一個假設，那就是要删除的結點存在連結清單當中。

測試用例：

1. 功能測試：删除多個結點連結清單的中間結點，頭結點，尾結點等；從隻有一個結點的連結清單中删除唯一結點。
2. 特殊輸入測試：