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() 

References

  1. 删除链表中的节点