如何在不交换链表节点的情况下使用冒泡排序？交换值实现问题咨询

你的代码存在三个核心问题，导致无法得到预期排序结果：

1. 比较逻辑完全错误
   冒泡排序的核心是每一轮将未排序区间的最大元素逐步“冒”到末尾，需要比较相邻节点的大小，但你代码里是把p2遍历到的所有节点和p1当前节点的值比较，这完全违背了冒泡排序的逻辑，会导致排序混乱。

2. 打印链表的参数错误
   外层循环结束后，p1已经走到链表的末尾（NULL），此时调用print_ll(p1)相当于打印空链表，应该传入链表头节点head才能输出整个排序后的链表。

3. 内层循环的遍历范围错误
   原代码内层循环每次都遍历整个链表，而冒泡排序每一轮只需要遍历未排序的区间，不需要重复处理已经排好序的末尾部分。

修正后的代码 #

struct node
{
    int data;
    struct node *next;
};

void sort_ll(struct node *head){
    if (head == NULL || head->next == NULL) {
        return; // 空链表或只有一个节点，无需排序
    }

    struct node *p1 = NULL;
    int swapped; // 标记是否发生交换，优化排序效率

    do {
        swapped = 0;
        struct node *p2 = head;

        while (p2->next != p1) { // 遍历到已排序区间的前一个节点
            if (p2->data > p2->next->data) {
                // 交换两个节点的值
                int temp = p2->data;
                p2->data = p2->next->data;
                p2->next->data = temp;
                swapped = 1;
            }
            p2 = p2->next;
        }
        p1 = p2; // 每轮结束后，p1指向已排序的末尾节点
    } while (swapped); // 没有交换发生时，说明链表已完全有序

    print_ll(head); // 传入头节点打印整个链表
}

修正说明 #

• 增加了空链表和单节点的边界判断，避免空指针访问。
• 使用swapped标记优化排序，当某一轮没有发生交换时，说明链表已经有序，可以提前结束排序。
• 内层循环只遍历未排序区间（到p1之前的节点），每轮结束后p1向前移动，缩小未排序范围。
• 正确比较相邻节点的值并交换，符合冒泡排序的核心逻辑。
• 打印时传入头节点head，确保输出整个排序后的链表。

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