# -*- coding: utf-8 -*-
# @Time : 2019-04-19 21:21
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : deleteNode.py
# @Blog : https://blog.51cto.com/jayce1111
# @GitHub : https://github.com/SysuJayce
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def deleteNode1(head, toBeDeleted):
"""普通的遍历, 复杂度为 O(n)"""
if not head or not toBeDeleted:
return
if head == toBeDeleted: # 如果待删除节点就是头节点, 那么就直接删除头节点即可
return head.next
# 维护一个指针, 目的是找到待删除节点的前一个节点, 因此我们遍历整个链表, 如果当前节点的下一个
# 节点就是待删除节点, 说明当前节点就是待删除节点的前一个节点, 我们直接将当前节点和待删除节点
# 的下一个节点连接起来即可
temp = head
while temp.next:
if temp.next == toBeDeleted:
temp.next = toBeDeleted.next
break
temp = temp.next
return head
def deleteNode(head, toBeDeleted):
"""
在 O(1) 时间内删除链表中的某个节点, 由于需要在 O(1) 时间内删除链表中的某个节点, 那么判断
toBeDeleted 这个节点是否在链表内的任务就无法完成, 需要调用者来判断.
"""
if not head or not toBeDeleted:
return
if head == toBeDeleted: # 待删除的节点是头节点
return head.next
# 待删除的节点是尾节点, 由于我们直接将 toBeDeleted 置为 None 无法真正改变链表中的节点, 因此需要
# 顺序查找, 这种情况下的时间复杂度为 O(n)
if not toBeDeleted.next:
temp = head
while temp.next:
if temp.next == toBeDeleted:
temp.next = toBeDeleted.next
break
temp = temp.next
# 待删除的节点是中间节点, 直接将下一个节点的值赋值给待删除节点, 然后将待删除节点和下下个节点
# 连接起来, 相当于是把待删除节点给删除了 (因为我们把待删除节点的下一个节点的值赋给了待删除节点)
else:
toBeDeleted.val = toBeDeleted.next.val
toBeDeleted.next = toBeDeleted.next.next
return head
def main():
zero = ListNode(0)
one = ListNode(1)
two = ListNode(2)
three = ListNode(3)
four = ListNode(4)
zero.next = one
one.next = two
two.next = three
three.next = four
phead = deleteNode(four, four)
while phead:
print(phead.val)
phead = phead.next
if __name__ == '__main__':
main()
来源: http://www.bubuko.com/infodetail-3032153.html