题目:给定单向链表的头指针和一个节点指针,在O(1)时间内删除链表节点。
def delete_list_node(root,rp): # 只有一个结点的情况 if root == rp: root = root.next del rp return root # 删除的是最后一个结点的情况 if rp.next == None: q = root while q.next!=rp: q=q.next q.next = None del rp return root else: q = rp.next rp.data = q.data rp.next = q.next del q return root
注:
情况1:删除的是头节点,直接返回head.next。(这种情况包含链表只有一个头节点的情况)
情况2:删除的是链表的最后一个节点,需要先遍历链表,获取要删除节点的前驱节点,然后将该节点指针指向None,删除节点
情况3:删除的是中间节点,将该节点后继节点的值复制给当前节点,然后让指针指向后继的后继