Description
给定单向链表的头指针和一个结点指针，定义一个函数在 $O(1)$ 时间删除该节点。
Solutions
需要注意的是，要看如何去操作，是判断结点的取值，还是直接对结点是否相等做判断。注意 $O(1)$ 实现方式的思路：
- 如果要删除结点不是最后一个结点，将下一个结点的内容覆盖当前结点
- 如果要删除的结点是最后一个结点，需要从头遍历
- 如果链表只有一个结点，需要单独处理
- 整体的时间复杂度是 $[(n-1)\times O(1) + O(n)]/n$，结果还是 $O(1)$
# coding: utf-8
# Linked List
class ListNode(object):
"""docstring for LinkedListNode"""
def __init__(self, data):
super(ListNode, self).__init__()
self.data = data
self.next = None
class LinkedList(object):
# initialize head
def __init__(self):
super(LinkedList, self).__init__()
self.head = None
# Function to insert a new node at the beginning
def insert_head(self, data):
new_node = ListNode(data)
new_node.next = self.head
self.head = new_node
# add a new node to this Linked List
def append(self, data):
if head is None:
self.head = ListNode(data)
else:
self.head.next = ListNode(data)
# Given a reference to the head of a list and a key,
# delete the first occurence of key in linked list
# O(n)，从判断值相等的角度来删除
def delete(self, node):
# Store the head node
tmp = self.head
# If the head node itself holds the key to be deleted
if tmp is not None:
if tmp.data == node.data:
self.head = tmp.next
tmp = None
return
prev = None
while tmp is not None:
if tmp.data == node.data:
break
prev = tmp
tmp = tmp.next
if tmp is None:
return
prev.next = tmp.next
tmp = None
# O(n)，从判断结点相同的角度来删除
def delete_node(self, node):
# Store the head node
tmp = self.head
# If the head node itself holds the key to be deleted
if tmp is not None:
if tmp == node:
self.head = tmp.next
tmp = None
return
prev = None
while tmp is not None:
if tmp == node:
break
prev = tmp
tmp = tmp.next
if tmp is None:
return
prev.next = tmp.next
tmp = None
# O(1)，判断结点是否相等
def quick_delete(self, node):
# 判断为空
if not (self.head and node):
return
if node.next is None:
# 如果只有一个结点
if self.head == node:
self.head = node = None
else:
tmp = self.head
while tmp.next:
if tmp.next == node:
tmp.next = node.next
del node
tmp = tmp.next
else:
node.data = node.next.data
next_node = node.next
node.next = next_node.next
del next_node
def get_node_by_val(self, val):
tmp = self.head
while tmp:
if tmp.data == val:
return tmp
tmp = tmp.next
return None
# Utility function to print the linked LinkedList
def printList(self):
temp = self.head
while temp:
print " %d" %(temp.data),
temp = temp.next
# Driver program
llist = LinkedList()
llist.insert_head(7)
llist.insert_head(1)
llist.insert_head(3)
llist.insert_head(2)
print "Created Linked List: "
# d_node = ListNode(1)
d_node = llist.get_node_by_val(1)
llist.printList()
# llist.delete(d_node)
# llist.delete_node(d_node)
llist.quick_delete(d_node)
print "\nLinked List after Deletion of 1:"
llist.printList()