Python 算法之 删除和移除(╯‵□′)╯链表中的元素『花样玩法』

Python 算法之 移除和删除(╯‵□′)╯链表中的元素『花样玩法』

---

一、链表中删除和移除的区别🥟

在链表中删除元素往往意味着删除一个或多个同样的节点，这取决于要求是什么，并不会把需要删除的元素在链表中全部删除，而移除与删除的差别就在这，移除会把指定的元素在链表中全部删除

无论是删除还是移除，都会使用到指针，指针分为 🥩

---

二、创建一个合适的链表👹

要删除和移除链表中的元素，最起码得先有一个链表吧，很多算法网站里已经有自带的链表对象，列如leetcode(力扣)中有已经写好的链表ListNode对象，不需要我们再去自己写一个，可有没有想过或者明白自己如何去创建一个链表呢？

对于单向链表来说，它包含两个域，一个信息域和一个指针域，信息域存放当前链表的值，指针域指向链表中的下一个节点，链表最后一个节点的指向是一个空值

以上信息已经足够说明，如何去定义一个链表的节点，这里写一个定义节点的类

class Node:
    def __init__(self, val=0, next=None):
        """
        链表节点
        :param val: 节点信息元素, 默认为0
        :param next: 下一节点的指向, 默认为None
        """
        self.val = val
        self.next = next

你可能会很惊讶，这么简单就能定义一个链表节点吗，是的，就是这么简单
再通过对象的实例化，一个简单的链表就创建完成了

node1, node2 = Node(), Node(1)
node1.next = node2
print(node1.val, node1.next.val)

但对于我们需要讲解的内容来说，这种程度的链表完全不够用，那么假设我已经创建了一个合适的链表ListNode，详情参考，并将其用于下面的内容中

---

三、删除链表中的元素👺

链表表中删除一个元素，其实就是更改这个元素的上一个元素下一指向，需要做的就是判断元素的值是否为目标值，并获取上一元素

除了更改被删除元素的上一个元素下一指向，还能将被删除元素的值和下一指向进行替换，这也能实现删除操作

在开始循环之前得保证表头的值不是目标值，循环可以获取链表中的元素，但判断是从第二个元素开始判断，这是因为需要获取上一元素值的话就得有所保留，对于不同的删除需求，有着不一样的处理方法，详情见下面内容

(一)、删除第一个指定元素

因为是删除第一个元素，如果表头的值就是目标值，那处理起来就非常简单了，直接返回下一指向即可

if head.val == val:
        return head.next

如果表头的值不是目标值，那就得循环判断后面的元素哪个是需要删除的目标，并更改其上一元素的下一指向

• 双指针方法

  思路： 先判断表头的值是否为目标值，定义两个指针，上一元素 prev = head 和 当前元素 curr = head.next，此时上一元素 prev 即为排除过的表头，通过循环判断当前元素 curr 的值是否为删除的目标值：

  • 如果是，则将上一元素 prev 的下一指向更改为当前值 curr 的下一指向 prev.next = curr.next，并返回整个链表
  • 如果不是，则移动指针 prev = curr curr = curr.next

  def deleteNode(head, val):
      if head.val == val:					# 判断表头的值是否为目标值
          return head.next
      prev, curr = head, head.next		# 定义上一指针 和 当前指针
      while curr:							# 当前指针不为空
          if curr.val == val:
              prev.next = curr.next
              return head					# 立即返回整个链表
          prev, curr = curr, curr.next
      return head
  

  • 时间复杂度: O(n)
    n为链表长度，最差情况下循环n次，最佳情况下为O(1)，即第一个元素为目标值
  • 空间复杂度: O(1)
    prev 和 curr 两个变量 占 常数大小空间

• 单指针方法

  要点： 在讲解思路之前，要明确删除元素的原理是，将上一元素的下一指向 更改为被删除元素的下一指向，通过更改指向的方式实现删除，那么关键就是获取上一元素 和 当前元素的下一节点。
  在上面的双指针方法中，上一节点 是通过变量(prev) 的方式存储获取的，当前节点(curr) 的下一指向，是通过 curr.next 属性获取的，那么思考一个问题，能不能通过 上一指针(prev) 获取当前节点(curr) 的下一指向呢？prev.next == curr
  很简单，既然 next属性 是获取下一指向，那么next 两次不就是获取下一指向的下一指向了吗 ! prev.next.next == curr.next

  思路： 还是先判断表头是否为目标值，只需要定义一个指针 curr， 此时指针 curr 代表着 双指针的 prev，curr.next 取到当前元素，通过循环判断当前元素 curr 的值是否为删除的目标值：

  • 如果是，则将 curr 的下一指向更改为 curr.next.next ，并返回整个链表
  • 如果不是，则移动指针 curr = curr.next，注意与双指针不同的是需要用到 else

  def deleteNode(head, val):
      if head.val == val:
          return head.next
      curr = head
      while curr.next:
          if curr.next.val == val:
              curr.next = curr.next.next
              return head
          else:
              curr = curr.next
      return head
  

  • 时间复杂度: O(n)
    n为链表长度，最差情况下循环n次，最佳情况下为O(1)，即第一个元素为目标值
  • 空间复杂度: O(1)
    curr 变量 占 常数大小空间

• 替换方法

  要点： 和单指针方法差不多，不同的是删除元素的方式，使用的是替换操作
  思路： 还是先判断表头是否为目标值，通过循环更改指针，结束循环的条件要不就是当前指针下一指向为空，要不就是下一指向为目标元素。此时指针为目标元素的上一元素，判断当前指针的下两个指向是否为空：

  • 如果为空，则直接将指针的下一指向 更改为None 即可，更改链表表尾
  • 如果不为空，替换元素值 和 元素下一指向

  def deleteNode(head, val):
      if head.val == val:
          return head.next
      curr = head
      while curr.next and curr.next.val != val:
          curr = curr.next
  
      if curr.next:
          if curr.next.next:
              curr.next.val = curr.next.next.val
              curr.next.next = curr.next.next.next
          else:
              curr.next = None
      return head
  

  • 时间复杂度: O(n)
    n为链表长度，最差情况下循环n次，最佳情况下为O(1)，即第一个元素为目标值
  • 空间复杂度: O(1)
    curr 变量 占 常数大小空间

(二)、删除倒数第一个指定元素

对于删除倒数元素来说，表头分两种情况，一种是使用反转链表的方法，那么最后一个元素就是表头，对其处理即可

• 反转链表

  删除倒数第一个指定元素，比较容易想到的方法是先反转链表，那么第一个碰到的目标元素就是倒数第一个目标元素，将其删除，最后再次反转链表恢复原顺序即可

  在讲解实际代码之前，得先明白如何去反转链表
  
  反转链表原理： 其实很简单，用到了双指针，上一指针和当前指针的初始值 分别为 prev=None curr=head，通过循环，每次都将当前指针的下一指向 curr 更改为上一指针 prev，直到当前指针 curr 遇到None，既为原链表最后元素的空指向，结束循环。

  难点在与，以往是通过 curr.next 方法获取到链表下一元素，可当前指针 curr 更改下一指向后，此方法就不可行了，如何再获取到链表下一元素？ 可行的方法是，先定义一个临时变量先将 curr.next 存起来，再通过这个临时变量获取链表下一元素

  def reverseNode(node):
      prev, curr = None, node
      while curr:
          temp = curr.next
          curr.next = prev
          prev, curr = curr, temp
      return prev
  

  反转完链表后，再使用之前 (一)、删除第一个指定元素 中说到过的方法处理即可，最后再还原链表返回。
  下面使用单指针方法👇

  def deleteNode(head, val):
  
      def reverseNode(rev_head):
          prev, curr = None, rev_head
          while curr:
              temp = curr.next
              curr.next = prev
              prev, curr = curr, temp
          return prev
  
      head = reverseNode(head)
  
      curr = head
      if curr.val == val:
          return reverseNode(curr.next)
  
      while curr.next:
          if curr.next.val == val:
              curr.next = curr.next.next
              return reverseNode(head)
          else:
              curr = curr.next
      return reverseNode(head)
  

  需要注意的是，反转链表后，要明确反转的链表放到了哪里？
  
  在没反转链表之前，head 变量为原链表的表头，它能获取到所有元素，可反转链表后，原来的表头已经没有下一指向，不再是反转链表的表头
  那反转链表的表头到底是谁？这时候应该想想，链表是从哪里开始不断添加元素的呢？或则说哪个变量存储到了最后一个循环的元素？
  

(三)、删除链表中的节点

如果只给定链表中的其中一个元素，没有表头，没有指定值，就只是删除给定的这个元素，你会怎么去做？

其实很简单，参考上面讲过的替换删除方法，这是一种不需要上一指针的方法

def deleteNode(node):
    if node.next:               # 如果拥有下一指向
        node.val, node.next = node.next.val, node.next.next
    else:                       # 如果不拥有下一指向
        node = None

---

---

四、移除链表中的元素👺

和删除元素一样，在开始循环之前得保证表头的值不是目标值，但是与删除不同的是，移除链表的元素得将元素全部删除，而不是只删除一个或指定的数量

如何保证表头的值不是目标值呢？ 在删除链表中，如果表头就是目标元素，那么直接返回表头的下一指向即可，但移除元素，这意味着得循环检索完链表中的全部元素，如果表头就是目标值，删除表头之后的下一指向有两种情况：

• 新的表头还是目标值，这意味着还得再次删除
• 新的表头不是目标值，这意味着可以开始循环

总结要点：

1. 需要循环检索整个链表
2. 保证表头的值不是目标，即使是删除后的新表头也一样

循环检索整个链表，这很简单不过多讲解，如何处理表头这是要点，主要有两种方法：

• 保证表头值方法

  要点： 循环判断更改表头，直到保证表头的值不为目标值 或 链表元素为空，这需要再多一个循环

  def removeElements(head, val):
     while head and head.val == val:
         head = head.next
     if not head:
         return None
  

  思路： 先处理表头，使用循环判断表头的值是否为目标值，如果是则更改表头，结束条件为表头的值不为目标值或链表为空，因为存在链表为空的情况，所以在正式遍历链表元素之前得先判断是否为空，若为空直接返回None，使用单指针方法，通过循环判断当前元素 curr 的值是否为删除的目标值：

  • 如果是，则将 curr 的下一指向更改为 curr.next.next
  • 如果不是，则移动指针 curr = curr.next，注意与双指针不同的是需要用到 else

  
  循环结束后将链表返回

  def removeElements(head, val):
  	while head and head.val == val:
  		head = head.next
      if not head:
          return None
  
      curr = head
  
      while curr.next:
          if curr.next.val == val:
              curr.next = curr.next.next
          else:
              curr = curr.next
      return head
  

• 添加哨兵节点方法

  要点： 最直接的方法，既然无法保证表头的值不是目标值，那自己新建一个节点作为表头。这个新建的节点，可以称作为 哨兵节点(sentinel) 或则称为 临时表头

  class ListNode:
  def __init__(self, val=0, next=None):
      self.val = val
      self.next = next
  
  
  def removeElements(head, val):
       sentinel = ListNode(val=-1, next=head)
  

  思路： 新建一个节点作为表头，无论这个节点的值是否为目标值，通过循环判断当前元素 curr 的值是否为删除的目标值：

  • 如果是，则将 curr 的下一指向更改为 curr.next.next
  • 如果不是，则移动指针 curr = curr.next，注意与双指针不同的是需要用到 else

  
  循环结束后将临时表头的下一指向返回， 这个临时表头不参与计算，起初始化作用

  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
  
  def removeElements(head, val):
       sentinel = ListNode(val=-1, next=head)
       curr = sentinel
       while curr.next:
           if curr.next.val == val:
               curr.next = curr.next.next
           else:
               curr = curr.next
       return sentinel.next
  

---

参考资料💌

• 题目出之力扣：
  • 删除链表的节点 剑指 Offer 18
  • 反转链表 剑指 Offer 24
  • 移除链表元素 leetcode 203
  • 删除链表中的节点 leetcode 237
• 链表 维基百科

由衷感谢💖

---

相关博客😏

• Python 算法之 动态规划详解
• Python 关于浮点数取整详解

转载：https://blog.csdn.net/XianZhe_/article/details/115795881