从链表中移除所有质数：现有代码仅删除单个质数的问题修正

原代码的核心问题 #

• is_prime函数参数设计错误，它应该接收单个数字而非链表，且未处理1不是质数的边界情况
• 主函数仅尝试删除最后一次生成的随机数，没有遍历整个链表删除所有质数节点

修复后的完整代码 #

import random
from linkListDef import * 

def is_prime(num):
    # 处理1及以下的数，都不是质数
    if num <= 1:
        return False
    # 2是唯一的偶质数
    if num == 2:
        return True
    # 偶数直接排除
    if num % 2 == 0:
        return False
    # 遍历到num的平方根即可，优化判断效率
    for count in range(3, int(num**0.5) + 1, 2):
        if num % count == 0:
            return False
    return True

def main():
    llist = LinkedList()
    # 生成20个1-100的随机数并构建链表
    for _ in range(20):
        num = random.randrange(1, 101)
        llist.push(num)
    
    print("Created Linked List: ")
    llist.printList()

    # 遍历链表删除所有质数节点
    prev = None
    current = llist.head  # 假设LinkedList类有head属性指向头节点
    while current:
        if is_prime(current.data):  # 假设节点类有data属性存储数值
            # 处理头节点删除的情况
            if prev is None:
                llist.head = current.next
            else:
                prev.next = current.next
            # 删除后prev不移动，current跳至下一个节点
            current = current.next
        else:
            # 非质数节点，同时移动prev和current指针
            prev = current
            current = current.next

    print("Linked List after Deletion of primes:")
    llist.printList()

if __name__ == '__main__':
    main()

关键修复点说明 #

1. 质数判断函数优化

   • 修正参数为单个数字，补充1、2、偶数等边界场景的处理
   • 将遍历范围缩小至数值的平方根，大幅提升判断效率

2. 链表遍历删除逻辑

   • 使用prev前驱节点跟踪当前节点的前一个节点，避免删除节点后链表断链
   • 逐个检查每个节点的数值，是质数则直接删除，直到遍历完整个链表

3. 适配注意事项

   • 确保linkListDef.py中的链表节点类包含data和next属性
   • 无论push方法是向头部还是尾部添加节点，删除逻辑都能正常工作，仅影响链表的初始顺序

内容的提问来源于stack exchange，提问作者user19986843