链表选择排序（交换节点实现）出现AttributeError问题求助

问题背景 #

要求通过交换节点而非值实现链表的选择排序，但排序时修改最后一个节点会触发AttributeError，报错显示'NoneType' object has no attribute 'next'，原代码及报错信息如下：

原代码 #

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

    def __init__(self, seq):
        self.front = self.Node(None)
        curr = self.front
        for value in seq:
            curr.next = self.Node(value)
            curr = curr.next

    def swap(self, x, y):
        first = self.front
        while first.next is not None:
            if first.next.data == x.data:
                prevx = first
            if first.next.data == y.data:
                prevy = first
            first = first.next
        x, y = y, x
        prevx.next, prevy.next = x, y
        temp = x.next
        x.next = y.next
        y.next = temp

    def progress(self, first, reverse):
        try:
            solid = first
            while first.next is not None:
                if solid.data > first.next.data and not reverse:
                    self.swap(solid, first.next)
                elif solid.data < first.next.data and reverse:
                    self.swap(solid, first.next)
                first = first.next
        except Exception:
            pass

    def min_sort(self, reverse):
        first = self.front
        while first.next is not None:
            self.progress(first, reverse)
            first = first.next


def min_sort(seq, reverse=False):
    ll = LinkedList(seq)
    ll.min_sort(reverse)
    return ll.get_list()


if __name__ == '__main__':
    seq = (4, 30, 8, 31, 48, 19)
    lst = min_sort(seq)
    print(lst)

报错信息 #

Traceback (most recent call last):
  File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 66, in <module>
    lst = min_sort(seq)
          ^^^^^^^^^^^^^
  File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 60, in min_sort
    ll.min_sort(reverse)
  File "/Users/rival/My files/Škola/FMFI UK/2. semester/Programovanie 2/projekt8/riesenie.py", line 46, in min_sort
    while first.next is not None:
          ^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'

错误原因分析 #

1. progress方法的solid赋值错误：solid = first中，first是哑节点（dummy node），其data为None，和有效节点比较会引发逻辑错误，且交换后可能导致first指针指向None。
2. swap方法的前驱查找逻辑缺陷：通过data匹配前驱节点，若链表存在重复值会找错前驱；且遍历整个链表后，若x或y是尾节点，后续交换可能破坏链表结构，导致first指针变成None。
3. min_sort循环条件漏洞：当first移动到尾节点时，first.next为None，但循环结束后first = first.next会让first变成None，下一次循环判断first.next就会触发报错。
4. 缺失get_list方法：原代码没有实现将链表转为列表的方法，无法返回排序结果。

修复方案 #

关键修改点 #

1. 修正progress方法的solid赋值：将solid = first改为solid = first.next，确保从有效节点开始比较；同时记录solid的前驱，避免后续交换时重新查找。
2. 改进swap方法：直接传入两个节点的前驱，避免通过data查找，同时处理相邻节点交换的特殊情况，保证链表结构完整。
3. 调整min_sort循环逻辑：循环条件改为first.next is not None and first.next.next is not None，避免first移动到尾节点后变为None；同时遵循选择排序核心逻辑，一次遍历找最值后仅交换一次，减少不必要操作。
4. 实现get_list方法：遍历链表，将节点数据转为列表返回。

修复后的完整代码 #

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

    def __init__(self, seq):
        self.front = self.Node(None)
        curr = self.front
        for value in seq:
            curr.next = self.Node(value)
            curr = curr.next

    def swap(self, prev_x, prev_y):
        # 获取要交换的两个节点
        x = prev_x.next
        y = prev_y.next

        # 处理x和y相邻的情况
        if x.next == y:
            prev_x.next = y
            x.next = y.next
            y.next = x
        elif y.next == x:
            prev_y.next = x
            y.next = x.next
            x.next = y
        else:
            # 不相邻的情况
            prev_x.next, prev_y.next = y, x
            x.next, y.next = y.next, x.next

    def progress(self, first, reverse):
        if first.next is None:
            return
        # solid是当前要放置最值的节点，prev_solid是其前驱
        prev_solid = first
        solid = first.next
        current_prev = first
        current = first.next

        while current is not None:
            # 找最小值（默认）或最大值（reverse=True）
            if (not reverse and current.data < solid.data) or (reverse and current.data > solid.data):
                prev_solid = current_prev
                solid = current
            current_prev = current
            current = current.next

        # 找到最值后，只交换一次（选择排序的核心）
        if prev_solid != first:
            self.swap(first, prev_solid)

    def min_sort(self, reverse):
        first = self.front
        # 循环到倒数第二个节点即可，最后一个节点无需处理
        while first.next is not None and first.next.next is not None:
            self.progress(first, reverse)
            first = first.next

    def get_list(self):
        result = []
        curr = self.front.next
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result


def min_sort(seq, reverse=False):
    ll = LinkedList(seq)
    ll.min_sort(reverse)
    return ll.get_list()


if __name__ == '__main__':
    seq = (4, 30, 8, 31, 48, 19)
    lst = min_sort(seq)
    print(lst)  # 输出: [4, 8, 19, 30, 31, 48]
    reversed_lst = min_sort(seq, reverse=True)
    print(reversed_lst)  # 输出: [48, 31, 30, 19, 8, 4]

说明 #

• 修复后的代码严格遵循选择排序逻辑：每次遍历找到未排序部分的最值节点，仅交换一次到正确位置，而非每次比较都交换。
• swap方法处理了相邻和非相邻节点的交换情况，保证链表结构不会被破坏。
• min_sort的循环条件避免了first指针变为None的情况，从根源上解决了AttributeError。

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