合并两个有序链表报AttributeError: NoneType对象无next属性

报错信息 #

运行合并两个有序链表功能时触发如下报错：

File "main.py", line 90, in <module>
    newHead = mergeTwoSortedLinkedLists(head1, head2)
  File "main.py", line 30, in mergeTwoSortedLinkedLists
    dummy.next=head2
AttributeError: 'NoneType' object has no attribute 'next'

测试用例信息 #

• 测试输入

LL1: 10 10 22 -1
LL2: 3 8 8 36 -1

• 预期输出

3 8 8 10 10 22 36

原代码问题点 #

原问题代码如下：

def mergeTwoSortedLinkedLists(head1, head2):
    
        # Write your code here
        if head1 is None and head2 is None:
            return None
        if head1 is None:
            return head2
        if head2 is None:
            return head1
        
        dummy=curr=None
      
        while head1 and head2:
            if head1.data<head2.data:
                #print("head1: ",head1.data)
                dummy.next=head1
                head1=head1.next
               
            else:
                #print("head2 :",head2.data)      
                dummy.next=head2
                head2=head2.next
            dummy=dummy.next
        if head1 is None:
            dummy.next=head2
        else:
            dummy.next=head1         
        
        
        return curr.next

核心逻辑错误有2处：

1. 指针初始化错误：dummy=curr=None直接将两个指针赋值为空值，第一次进入循环执行dummy.next=xxx赋值操作时，None类型不存在next属性，直接触发本次看到的属性报错。
2. 指针职责混淆：哑节点（dummy）的作用是固定在合并后链表的最前端，避免单独处理头节点插入的边界逻辑，需要单独用一个移动指针（curr）从哑节点位置开始向后遍历拼接节点，原代码直接移动dummy指针，且返回值取始终为None的curr.next，就算解决初始化问题也无法得到正确的链表头。

修复后代码 #

# 注：ListNode为链表节点通用定义，若题目环境已内置可省略
class ListNode:
    def __init__(self, data=0, next=None):
        self.data = data
        self.next = next

def mergeTwoSortedLinkedLists(head1, head2):
    # 空链表边界判断
    if head1 is None and head2 is None:
        return None
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    
    # 初始化无业务数据的哑节点，移动指针curr初始指向哑节点
    dummy = ListNode()
    curr = dummy
      
    while head1 and head2:
        if head1.data < head2.data:
            curr.next = head1
            head1 = head1.next
        else:      
            curr.next = head2
            head2 = head2.next
        curr = curr.next
    # 拼接剩余未遍历完成的有序链表段
    curr.next = head2 if head1 is None else head1
    
    # 哑节点的下一个节点就是合并后链表的真正头节点
    return dummy.next

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