Python在O(1)时间删除链表结点
当要删除的结点不是尾结点而且不是仅有一个结点的头结点,可以把该结点i的下一个结点j的内容复制到结点i,同时把i结点的next指向j结点的next,然后再删除结点j。如果要删除的链表为单结点链表且待删除的结点就是头结点,需要把头结点置为None,如果删除的结点为链表的尾结点,那么就需要顺序遍历链表,找到尾节点前面一个结点,然后将其next置空。
- '''
- 给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点
- '''
- class ListNode:
- def __init__(self, x=None):
- self.val = x
- self.next = None
- def __del__(self):
- self.val = None
- self.next = None
-
- class Solution:
- def DeleteNode(self, pListHead, pToBeDeleted):
- if not pListHead or not pToBeDeleted:
- return None
-
- if pToBeDeleted.next != None:
- pNext = pToBeDeleted.next
- pToBeDeleted.val = pNext.val
- pToBeDeleted.next = pNext.next
- pNext.__del__()
-
-
- elif pListHead == pToBeDeleted:
- pToBeDeleted.__del__()
- pListHead.__del__()
- else:
- pNode = pListHead
- while pNode.next != pToBeDeleted:
- pNode = pNode.next
- pNode.next = None
- pToBeDeleted.__del__()
-
-
- node1 = ListNode(10)
- node2 = ListNode(11)
- node3 = ListNode(13)
- node4 = ListNode(15)
- node1.next = node2
- node2.next = node3
- node3.next = node4
-
- S = Solution()
- S.DeleteNode(node1, node3)
- print(node3.val)
- S.DeleteNode(node1, node3)
- print(node3.val)
- print(node2.val)
- S.DeleteNode(node1, node1)
- print(node1.val)
- S.DeleteNode(node1, node1)
- print(node1.val)
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。