如何通过调整节点位置排序已有的双向循环链表（不修改节点数据）

问题背景 #

在大学《数据结构》课程期末考试中，题目要求补全给定代码中的node_sorting函数，实现双向循环链表的排序。我采用冒泡排序思路，通过交换节点的data值完成了函数编写，但教授判定该答案得0分，指出此方法属于“投机取巧”，在实际场景中可能引发严重问题，要求必须不修改节点数据，仅通过调整节点的位置来实现排序。查阅一周资料后，找到的均是关于有序双向循环链表插入节点的内容，未找到适配现有双向循环链表的排序方法，特此求助正确的实现方案。

考试给定代码框架 #

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node* next;
    struct Node* pre;
};

struct Node* node_create(int data)
{
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;
    new_node->pre = NULL;

    return new_node;
}

void node_add(struct Node** head, struct Node* new_node)
{
    struct Node* list = *head;

    if(*head == NULL)
    {
        new_node->next = new_node;
        new_node->pre = new_node;
        *head = new_node;
    }
    else
    {
        while(list->next != *head)
        {
            list = list->next;
        }

        list->next = new_node;
        (*head)->pre = new_node;

        new_node->next = *head;
        new_node->pre = list;
    }
}

void node_list(struct Node** head)
{
    struct Node* list = *head;

    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    do{

        //printf("(%p) %p - %d-> (%p)", list->pre,list,list->data,list->next);
        printf("%d-> ", list->data);
        list = list->next;
    }while(list != *head);
}

void node_delete(struct Node** head, int data)
{
    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    struct Node* list = *head;
    struct Node* end = *head;

    if( list->data == data )
    {
        if(list->next == list)
        {
            free(list);
            *head = NULL;
        }
        else
        {
            while(end->next != *head)
            {
                end = end->next;
            }

            *head = list->next;
            end->next = *head;
            (*head)->pre = end;
            free(list);
        }
    }
    else
    {
        while(list->data != data && list->next != *head)
        {
            list = list->next;
        }

        if(list->data != data && list->next == *head)
        {
            printf("No value for delete!\n");
            return;
        }

        (list->pre)->next = list->next;
        (list->next)->pre = list->pre;
        free(list);
    }

    printf("\nDelete of complited!\n");


}

void node_sorting(struct Node** head)
{
    
}




int main()
{
    struct Node* head = NULL;
    struct Node* new_node = NULL;
    int select = 0, data = 0, one = 1;

    while(one == 1)
    {
        printf("\n\nNode Add (1)\n");
        printf("Node List (2)\n");
        printf("Node Delete (3)\n");
        printf("Node Sorting (4)\n");

        printf("\nSelect: ");
        scanf("%d", &select);

        if(select == 1)
        {
            printf("\nData: ");
            scanf("%d", &data);

            new_node = node_create(data);
            node_add(&head, new_node);
        }
        else if(select == 2)
        {
            node_list(&head);
        }
        else if(select == 3)
        {
            printf("\nData to delete: ");
            scanf("%d", &data);

            node_delete(&head, data);
        }
        else if(select == 4)
        {
            node_sorting(&head);
        }

    }

    return 0;
}

我最初的错误实现代码 #

void node_sorting(struct Node** head)
{
    struct Node* list = *head;
    struct Node* tolist = *head;

    if(*head == NULL)
    {
        printf("\nEmpty Linked List!\n");
        return;
    }

    if((*head)->next == *head)
    {
        printf("A single-element linked list cannot be sorted.");
        return;
    }

    do{

        tolist = list->next;
        list = list->next;

        while(tolist != *head)
        {
            if(list->data > tolist->data)
            {
                int temp = 0;
                temp = tolist->data;
                tolist->data = list->data;
                list->data = temp;
            }
    
            tolist = tolist->next;
        }


    }while(list != *head);

}

正确实现方案（仅调整节点位置的冒泡排序） #

下面是符合要求的node_sorting函数实现，基于冒泡排序逻辑，通过调整节点的前后指针完成排序，不修改任何节点的data值：

void node_sorting(struct Node** head)
{
    if (*head == NULL || (*head)->next == *head) {
        if (*head == NULL)
            printf("\nEmpty Linked List!\n");
        return;
    }

    int swapped;
    struct Node* current;
    struct Node* last_sorted = *head; // 标记已排序部分的尾节点

    do {
        swapped = 0;
        current = *head;

        // 遍历到已排序部分的前一个节点
        while (current->next != last_sorted) {
            struct Node* next_node = current->next;

            // 如果当前节点数据大于下一个节点，交换两者位置
            if (current->data > next_node->data) {
                // 1. 移除next_node原位置的连接
                current->next = next_node->next;
                next_node->next->pre = current;

                // 2. 将next_node插入到current的前面
                next_node->pre = current->pre;
                current->pre->next = next_node;
                current->pre = next_node;
                next_node->next = current;

                // 如果current是头节点，更新头指针
                if (current == *head) {
                    *head = next_node;
                }

                swapped = 1;
                // 交换后current位置不变，因为next_node已经到前面了
            } else {
                current = current->next;
            }
        }
        last_sorted = current; // 本次排序后，最后一个节点已处于正确位置
    } while (swapped);
}

代码说明 #

1. 边界处理：先判断链表为空或只有单个节点的情况，直接返回（单个节点无需排序）。
2. 冒泡排序逻辑：通过swapped标记是否发生交换，若某次遍历无交换则说明链表已排序。
3. 节点位置调整：
   • 当需要交换current和next_node时，先断开next_node与原前后节点的连接。
   • 将next_node插入到current的前面，调整两者的pre和next指针。
   • 如果current是头节点，需要更新head指针，保证头节点始终指向链表的第一个元素。
4. 优化：用last_sorted标记已排序部分的尾节点，减少不必要的遍历次数。

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