文章目录

1. 题目2. 解题思路3. 代码实现4. 总结5. 参考文献

1. 题目

题目一：在O(1)时间内删除链表节点。 给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下：

struct ListNode { int m_nValue; ListNode* m_pNext; } void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted);

python实现的节点如下：

class ListNode: def __init__(self, value, next=None): self.value = value self.next = next

2. 解题思路

通常而言，要删除链表中的某个节点，需要做的是：根据head节点进行遍历，将需删除的节点的前一个节点的next指向需删除的节点的下一个节点即可。

# 要删除的节点为cur，前一个节点是pre pre.next = cur.next

但是，只要遍历链表，则不可能在O(1)内删除cur节点。

牛逼的来了，用cur.next这个节点覆盖掉cur节点就删除了cur了。

3. 代码实现

class Solution: def deleteNode(self, head, cur): """ head 为头节点，cur为要删除的节点 """ if not head or not cur: # 节点是否存在 return if cur.next: # 要删除的节点不为尾节点 cur.value = cur.next.value cur.next = cur.next.next elif head == cur: head = None else: # 要删除的节点是尾节点 temp = head while temp.next != cur: temp = temp.next temp.next = None

在这里，O(1)是平均时间复杂度。

4. 总结

其实，本题只要有了用后一个节点覆盖当前节点等价于删除当前节点这个思想就行了。

5. 参考文献

[1] 剑指offer丛书