首页 > 其他 > 详细

移除链表中的元素

时间:2020-09-03 13:59:12      阅读:62      评论:0      收藏:0      [点我收藏+]

移除链表元素

力扣 (LeetCode)发布于 2020-01-0323.0k官方JavaPythonC++

方法:哨兵节点

如果删除的节点是中间的节点,则问题似乎非常简单:

  • 选择要删除节点的前一个结点 prev
  • 将 prev 的 next 设置为要删除结点的 next

技术分享图片

当要删除的一个或多个节点位于链表的头部时,事情会变得复杂。

技术分享图片

可以通过哨兵节点去解决它,哨兵节点广泛应用于树和链表中,如伪头、伪尾、标记等,它们是纯功能的,通常不保存任何数据,其主要目的是使链表标准化,如使链表永不为空、永不无头、简化插入和删除。

技术分享图片

在这里哨兵节点将被用于伪头。

算法:

  • 初始化哨兵节点为 ListNode(0) 且设置 sentinel.next = head
  • 初始化两个指针 curr 和 prev 指向当前节点和前继节点。
  • 当 curr != nullptr
    • 比较当前节点和要删除的节点:
      • 若当前节点就是要删除的节点:则 prev.next = curr.next
      • 否则设 prve = curr
    • 遍历下一个元素:curr = curr.next
  • 返回 sentinel.next
  • 技术分享图片

     

     技术分享图片

     

     

     

 

移除链表中的元素

原文:https://www.cnblogs.com/sweet-li/p/13606849.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!