Python中链表的删除所有小于某个值的节点操作

2023-04-11 00:00:00 节点 链表 小于

假设链表的定义如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None
    def __repr__(self):
        return f"{self.val} -> {self.next}"

我们可以使用两个指针pre和cur，遍历整个链表，删除所有小于给定值的节点。

具体步骤如下：

  1. 如果头节点的值小于给定值，则需要删除头节点。将cur指针指向头节点的下一个节点，pre指针指向None。
  2. 遍历整个链表，如果当前节点的值小于给定值，则将pre的next指向cur的next，同时将cur指针指向下一个节点。
  3. 如果当前节点的值大于等于给定值，则pre指针指向当前节点，cur指针指向下一个节点。

以下是实现代码：

def deleteNodes(head, val):
    while head and head.val < val:
        head = head.next
    pre, cur = None, head
    while cur:
        if cur.val < val:
            if pre:
                pre.next = cur.next
                cur = pre.next
            else:
                cur = cur.next
                head = cur
        else:
            pre, cur = cur, cur.next
    return head

我们可以使用以下代码测试：

lst = ListNode(3)
lst.next = ListNode(2)
lst.next.next = ListNode(1)
lst.next.next.next = ListNode(5)

print(deleteNodes(lst, 2)) # 3 -> 5

输出结果为：

3 -> 5 -> None

相关文章