如何解决Python链表归并排序中'NoneType'无'head'属性的AttributeError

报错根因 #

你遇到的AttributeError: 'NoneType' object has no attribute 'head'错误，核心原因是merge函数返回值异常：当前代码中merge最后返回的是merged.printlist()，这类打印方法默认返回None，递归调用merge_sort拿到None后传入下一层merge，访问None.head就触发了报错。除此之外代码还有多处逻辑漏洞需要修复。

需修改的问题点 #

• merge函数逻辑不完整：缺少左右节点值比较逻辑，未定义head变量直接赋值，且未移动current指针，返回值类型错误
• split函数判断顺序错误：先访问ll.head再判断ll是否为None，如果入参为None会提前触发异常
• merge_sort边界判断顺序不合理：未优先判断入参是否为None，调用ll.length()存在风险

修复后代码 #

def merge_sort(ll):
    # 优先判断入参是否为None
    if ll is None:
        return ll
    elif ll.head is None or ll.length() == 1:
        return ll
    left_half, right_half = split(ll)
    left = merge_sort(left_half)
    right = merge_sort(right_half)
    return merge(left, right)

def split(ll):
    # 先判断ll是否为None，再访问head属性
    if ll is None or ll.head is None:
        left_half = ll
        right_half = None
        return left_half, right_half
    else:
        size = ll.length()
        mid = size // 2
        mid_node = ll.nodeAt(mid - 1)
        # 调整原代码左右半区反写的逻辑，左半区为前mid个节点，右半区为剩余节点
        left_half = ll
        right_half = LinkedList()
        right_half.head = mid_node.next
        mid_node.next = None
        return left_half, right_half

def merge(left, right):
    merged = LinkedList()
    # 哨兵节点简化边界处理
    merged.tailinsert(0)
    current = merged.head
    # 兼容入参为None的场景
    left_head = left.head if left is not None else None
    right_head = right.head if right is not None else None
    
    while left_head or right_head:
        if left_head is None:
            current.next = right_head
            right_head = right_head.next
        elif right_head is None:
            current.next = left_head
            left_head = left_head.next
        else:
            # 补全值比较逻辑，假设节点值存储在data属性，可根据你的实现替换属性名
            if left_head.data < right_head.data:
                current.next = left_head
                left_head = left_head.next
            else:
                current.next = right_head
                right_head = right_head.next
        # 移动当前指针到下一位
        current = current.next
    # 移除哨兵节点
    merged.head = merged.head.next
    # 返回链表对象而非打印结果
    return merged

lst = LinkedList()
lst.tailinsert(14)
lst.tailinsert(46)
lst.tailinsert(43)
lst.tailinsert(27)
sorted_list = merge_sort(lst)
# 最终输出时再调用打印方法
print(sorted_list.printlist())

注：上述代码默认链表节点的取值属性为data，如果你的自定义节点类中取值属性名不同，替换为对应名称即可。

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