Python在O(1)时间删除链表结点

本文阅读 1 分钟
首页 Python笔记 正文

当要删除的结点不是尾结点而且不是仅有一个结点的头结点,可以把该结点i的下一个结点j的内容复制到结点i,同时把i结点的next指向j结点的next,然后再删除结点j。如果要删除的链表为单结点链表且待删除的结点就是头结点,需要把头结点置为None,如果删除的结点为链表的尾结点,那么就需要顺序遍历链表,找到尾节点前面一个结点,然后将其next置空。

  1. '''
  2. 给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点
  3. '''
  4. class ListNode:
  5. def __init__(self, x=None):
  6. self.val = x
  7. self.next = None
  8. def __del__(self):
  9. self.val = None
  10. self.next = None
  11. class Solution:
  12. def DeleteNode(self, pListHead, pToBeDeleted):
  13. if not pListHead or not pToBeDeleted:
  14. return None
  15. if pToBeDeleted.next != None:
  16. pNext = pToBeDeleted.next
  17. pToBeDeleted.val = pNext.val
  18. pToBeDeleted.next = pNext.next
  19. pNext.__del__()
  20. elif pListHead == pToBeDeleted:
  21. pToBeDeleted.__del__()
  22. pListHead.__del__()
  23. else:
  24. pNode = pListHead
  25. while pNode.next != pToBeDeleted:
  26. pNode = pNode.next
  27. pNode.next = None
  28. pToBeDeleted.__del__()
  29. node1 = ListNode(10)
  30. node2 = ListNode(11)
  31. node3 = ListNode(13)
  32. node4 = ListNode(15)
  33. node1.next = node2
  34. node2.next = node3
  35. node3.next = node4
  36. S = Solution()
  37. S.DeleteNode(node1, node3)
  38. print(node3.val)
  39. S.DeleteNode(node1, node3)
  40. print(node3.val)
  41. print(node2.val)
  42. S.DeleteNode(node1, node1)
  43. print(node1.val)
  44. S.DeleteNode(node1, node1)
  45. print(node1.val)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python打印1到最大的n位数
« 上一篇 01-21
Python调整数组顺序使奇数位于偶数前面
下一篇 » 01-21

发表评论