Python实现按字符串值升序排序链表 冒泡排序死循环问题求解

原有代码的问题点 #

你写的排序方法存在4个基础逻辑错误，直接导致死循环和排序失效：

• 比较逻辑无效：判断条件写的是temp.song.song_name > temp.song.song_name，拿同一个节点的歌名和自己比较，结果永远为假，根本没有对相邻节点的值做对比
• 交换逻辑制造环：如果真的进入交换分支，你执行temp.next = prev的时候，没有调整前序节点的指向，直接让两个相邻节点的next指针互指，形成A→B→A的死循环，遍历到这里就永远出不来
• 冒泡排序结构缺失：标准冒泡排序需要多轮遍历，每轮把当前最大的元素沉到表尾，你只写了一层遍历，就算逻辑正确也没法完成全表排序
• 指针移动混乱：交换分支内已经移动过一次temp指针，分支外又无条件执行一次temp = temp.next，会直接跳过节点，甚至触发空指针访问错误

修正后的可运行代码 #

你已经实现的Song、ListNode类和LinkedList的其他方法不需要改动，只需要把原有错误的sort_linked_list方法替换为下面的实现即可：

import time

class Song:
    def __init__(self, song_id, song_name, song_length):
        self.song_id = song_id
        self.song_name = song_name
        self.song_length = song_length
        
    def __str__(self):
        return str({'song_id':self.song_id, 
                    'song_name':self.song_name, 
                    'song_length':self.song_length})
        

class ListNode:
    def __init__(self, song:Song):
        self.song = song
        self.next = None
        
    def __str__(self):
        return str(self.song)
    

class LinkedList:
    def __init__(self):
        self.head_node = None
        self.count = 0
    
    def traversal(self):
        if self.head_node is None:
            return
        
        temp_node = self.head_node
        
        while(temp_node != None):
            print(temp_node.song)
            time.sleep(2)
            temp_node = temp_node.next
        
        time.sleep(2)
        return
    
    def insert_at_start(self, node):
        if self.head_node is None:
            self.head_node = node
            self.count = self.count + 1
            return True
        
        node.next = self.head_node
        self.head_node = node
        
        return True
    
    def insert_after(self, song_name, node):
        temp_node = self.head_node
        
        while(temp_node.song.song_name!=song_name):
            temp_node = temp_node.next
          
        if temp_node is None:
            return False

        else:
            if temp_node.next == None:
                temp_node.next = node
            else:
                node.next = temp_node.next
                temp_node.next = node
            
            return True
    
    def insert_before(self, song_name, node):
        temp_node = self.head_node
        prev_node = None
        
        while(temp_node.song.song_name!=song_name):
            prev_node = temp_node
            temp_node = temp_node.next
        
        if temp_node == None:
            return False

        if prev_node == None:
            node.next = self.head_node
            self.head_node = node
            return True
        
        prev_node.next = node
        node.next = temp_node
        
        return True

    def sort_linked_list(self):
        # 空表或单节点直接返回，无需排序
        if self.head_node is None or self.head_node.next is None:
            return
        
        sorted_bound = None
        # 外层循环：直到已排序边界覆盖到表头，说明全表有序
        while sorted_bound != self.head_node:
            prev = None
            curr = self.head_node
            # 内层遍历：只走未排序区间，到已排序边界就停止
            while curr.next != sorted_bound:
                next_node = curr.next
                # 相邻节点逆序，需要交换位置
                if curr.song.song_name > next_node.song.song_name:
                    # 先把当前节点和后面的链路接上，避免断链
                    curr.next = next_node.next
                    next_node.next = curr
                    # 调整前序节点的指向
                    if prev is None:
                        # 交换的是头节点，更新表头指针
                        self.head_node = next_node
                    else:
                        prev.next = next_node
                    # 指针后移，准备下一轮比较
                    prev = next_node
                else:
                    # 无需交换，指针正常后移
                    prev = curr
                    curr = curr.next
            # 当前curr是这一轮找到的最大值，更新已排序边界
            sorted_bound = curr

实现逻辑说明 #

• 完全遵循冒泡排序核心逻辑：每轮遍历未排序区间，两两比较相邻节点，逆序就交换，每轮结束后确定一个最大值的最终位置，时间复杂度为O(n²)，适合小规模链表排序
• 全程维护三个指针prev/curr/next_node，调整指针时先接好后续链路再修改前序指向，从根源上避免环和断链问题
• 用sorted_bound标记已排序区间的起点，每轮遍历不需要重复遍历已经排好序的尾部节点，减少无效遍历
• 单独处理头节点交换的边界场景，不会出现表头丢失的问题

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