交替合并链表问题：报错排查与低效实现优化需求

问题分析 #

当前实现存在三个核心问题：

• AttributeError错误：当循环次数超过链表剩余节点数时，会访问NoneType的elem属性（例如两个链表长度相同时，最后一次循环会尝试访问已变为None的指针的elem）。
• 效率低下：提前遍历两次链表统计长度，额外增加了O(n+m)的时间开销；且返回合并后的尾节点而非头节点，导致打印结果完全错误。
• 未处理剩余节点：当其中一个链表更长时，剩余节点未被追加到合并链表中。

修复并优化后的代码 #

class Node:
    def __init__(self, elem, next=None):
        self.elem, self.next = elem, next

def createList(arr):
    head = Node(arr[0])
    tail = head
    for i in range(1, len(arr)):
        newNode = Node(arr[i])
        tail.next = newNode
        tail = newNode
    return head

def printLinkedList(head):
    temp = head
    while temp is not None:
        if temp.next is not None:
            print(temp.elem, end='-->')
        else:
            print(temp.elem)
        temp = temp.next
    print()

def alternate_merge(head1, head2):
    # 哑节点，简化头节点处理逻辑
    dummy = Node(None)
    current = dummy
    temp1 = head1
    temp2 = head2

    # 交替遍历两个链表，直到其中一个为空
    while temp1 is not None and temp2 is not None:
        current.next = Node(temp1.elem)
        current = current.next
        temp1 = temp1.next

        current.next = Node(temp2.elem)
        current = current.next
        temp2 = temp2.next

    # 追加第一个链表的剩余节点
    while temp1 is not None:
        current.next = Node(temp1.elem)
        current = current.next
        temp1 = temp1.next

    # 追加第二个链表的剩余节点
    while temp2 is not None:
        current.next = Node(temp2.elem)
        current = current.next
        temp2 = temp2.next

    # 返回合并后的链表头节点
    return dummy.next

# 测试用例
import numpy as np

print('==============测试用例1=============')
head1 = createList(np.array([1,2,6,8,11]))
head2 = createList(np.array([5,7,3,9,4]))

print("链表1:")
printLinkedList(head1)
print("链表2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("合并后的链表:")
printLinkedList(head)

print('==============测试用例2=============')
head1 = createList(np.array([5, 3, 2, -4]))
head2 = createList(np.array([-4, -6, 1]))

print("链表1:")
printLinkedList(head1)
print("链表2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("合并后的链表:")
printLinkedList(head)

print('==============测试用例3=============')
head1 = createList(np.array([4, 2, -2, -4]))
head2 = createList(np.array([8, 6, 5, -3]))

print("链表1:")
printLinkedList(head1)
print("链表2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("合并后的链表:")
printLinkedList(head)

关键改动说明 #

• 移除预统计长度步骤：直接在合并过程中遍历两个链表，避免额外两次遍历，将时间复杂度优化为O(n+m)（仅需一次遍历）。
• 修正交替逻辑：循环中依次添加两个链表的节点，直到其中一个链表遍历完毕，从根源避免空指针访问。
• 追加剩余节点：当其中一个链表先遍历完成，将另一个链表的剩余节点直接追加到合并链表尾部。
• 返回正确头节点：使用哑节点dummy简化头节点处理，最终返回dummy.next作为合并链表的头，确保打印结果符合预期。

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