如何在链表中使用冒泡排序而不交换节点？

Question

我正在尝试使用冒泡排序对链表进行排序。为什么我不能交换节点的值并产生所需的输出，而不是交换节点？下面的代码是我的方法。

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

void sort_ll(struct node *head){
    struct node *p1 = head;
    struct node *p2 = NULL;
    while(p1->next!=NULL){
        p2 = p1;
        int temp;
        while(p2->next!=NULL){
            if(p2->data>p1->data){
                temp = p2->data;
                p2->data = p1->data;
                p1->data = temp;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
    print_ll(p1);
}

Answer 1

交换链表中节点的值是对列表进行排序的有效方法，但您提供的代码存在一些问题，可能会导致问题。让我们逐步解决这些问题。

代码中的问题：

1. 不正确的比较逻辑：

   • 您正在内部循环中将

     p2->data

     与

     p1->data

     进行比较，这与典型的冒泡排序逻辑不一致。在冒泡排序中，每个元素都会与下一个元素进行比较，如果它们的顺序错误，则交换它们。在您的代码中，您应该将

     p2->data

     与

     p2->next->data

     进行比较。

2. 重置

   p2

   ：
   • 每次外循环迭代后，

     p2

     都会被设置为

     p1

     ，这意味着每次都从

     p1

     的当前位置开始内循环。这将导致排序不正确，因为冒泡排序算法要求您每次遍历都从列表的开头开始。

3. 遍历指针：

   • 对链表进行排序后，将

     p1

     传递给

     print_ll

     函数，该函数将在循环结束时为

     NULL

     。相反，您应该传递原始的

     head

     指针。

更正代码：

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

void sort_ll(struct node *head){
    struct node *p1 = NULL;
    struct node *p2 = NULL;
    int temp;

    // Check if the list is empty
    if (head == NULL)
        return;

    // Bubble sort logic
    for (p1 = head; p1->next != NULL; p1 = p1->next) {
        for (p2 = head; p2->next != NULL; p2 = p2->next) {
            if (p2->data > p2->next->data) {
                // Swap the data of the nodes
                temp = p2->data;
                p2->data = p2->next->data;
                p2->next->data = temp;
            }
        }
    }

    // Print the sorted linked list
    print_ll(head);
}

说明：

1. 外循环：外循环（

   for (p1 = head; p1->next != NULL; p1 = p1->next)

   ）迭代整个列表，确保每个元素“冒泡”到其正确的位置。

2. 内循环：内循环 (

   for (p2 = head; p2->next != NULL; p2 = p2->next)

   ) 将每个元素与列表中的下一个元素进行比较。如果

   p2->data

   大于

   p2->next->data

   ，则会交换值。

3. 交换数据：交换通过

   temp

   变量进行，其中交换节点的数据而不是交换节点本身。

4. 打印列表：排序后，调用

   print_ll(head)

   函数打印排序后的列表，从原始

   head

   开始。

总结：

交换链表中的值而不是节点是实现冒泡排序等排序算法的有效且简单的方法。原始代码中的关键问题与比较逻辑和遍历指针有关，这些问题已在提供的解决方案中得到纠正。此更正后的代码现在应该正确地按升序对链接列表进行排序。