【剑指offer】在O(1)时间复杂度下删除一个节点

爱被打了一巴掌 2022-05-14 14:53 170阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_27_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_27_color_FFFFFF_t_70 1]

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        def DeleteNode(self, head, node):
            if node.next != None:
                nextNode = node.next
                node.val = nextNode.val
                node.next = nextNode.next
                del nextNode
            elif head == node:
                del node
                head = None
            else:
                p = head
                while p.next != node:
                    p = p.next
                p.next = None
                del node

计算时间复杂度：  
对于尾节点而言，由于需要遍历时间复杂度为O(n)。因此总的时间复杂度为:  
\[O(1) X (n - 1) + O(n) X 1\] / n = O(1)。也就是说，特殊情况下需要遍历，但是总的时间复杂度仍然是符合要求的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_27_color_FFFFFF_t_70]: /images/20220504/8354616fad4e480aad8d95f10a0b773b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_27_color_FFFFFF_t_70 1]: /images/20220504/6c562999c7874adeb306cb0fae2be921.png