## Solutions

• 如果要删除结点不是最后一个结点，将下一个结点的内容覆盖当前结点
• 如果要删除的结点是最后一个结点，需要从头遍历
• 如果链表只有一个结点，需要单独处理
• 整体的时间复杂度是 $[(n-1)\times O(1) + O(n)]/n$，结果还是 $O(1)$
# coding: utf-8

class ListNode(object):
def __init__(self, data):
super(ListNode, self).__init__()
self.data = data
self.next = None

def __init__(self):

# Function to insert a new node at the beginning
new_node = ListNode(data)

def append(self, data):
else:

# 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):

# If the head node itself holds the key to be deleted
if tmp is not None:
if tmp.data == node.data:
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):

# If the head node itself holds the key to be deleted
if tmp is not None:
if tmp == node:
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):
# 判断为空
return

if node.next is None:
# 如果只有一个结点
else:
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):
while tmp:
if tmp.data == val:
return tmp
tmp = tmp.next

return None

def printList(self):
while temp:
print " %d" %(temp.data),
temp = temp.next

# Driver program