单链表排序后原链表缩短问题求助（不可修改函数原型）

问题根源 #

你当前的sortEmployee函数直接在原链表的节点指针上做交换操作（冒泡排序的链表实现），这会永久性改变原链表的节点连接关系。比如原链表中节点402原本指向809，排序后被改成指向524，同时原本在前面的100、106节点被移到了原链表头部的前面，但main里的head指针仍然指向原来的402节点，导致后续打印时只能从402开始往后遍历，丢失了前面的节点，这就是原链表“变短”的原因。

解决方案 #

要满足“仅在函数内打印排序结果、不修改原链表”的要求，正确的做法是：

• 先创建原链表的完整副本（包括所有节点的数据和依赖项）
• 对副本链表进行排序并打印
• 打印完成后释放副本链表的内存，避免内存泄漏

修改后的代码实现 #

1. 辅助函数：复制单个员工节点 #

先实现单个employee节点的复制，包括其依赖项：

struct employee* copyEmployeeNode(const struct employee* src) {
    if (src == NULL) return NULL;

    struct employee* newNode = (struct employee*)malloc(sizeof(struct employee));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        return NULL;
    }

    // 复制基本字段
    strncpy(newNode->fname, src->fname, MAX_LENGTH);
    strncpy(newNode->lname, src->lname, MAX_LENGTH);
    newNode->empId = src->empId;
    newNode->numDependents = src->numDependents;

    // 复制依赖项数组
    if (src->numDependents > 0) {
        newNode->dependents = (char**)malloc(src->numDependents * sizeof(char*));
        if (newNode->dependents == NULL) {
            free(newNode);
            printf("Memory allocation failed for dependents!\n");
            return NULL;
        }
        for (int i = 0; i < src->numDependents; i++) {
            newNode->dependents[i] = (char*)malloc(strlen(src->dependents[i]) + 1);
            strcpy(newNode->dependents[i], src->dependents[i]);
        }
    } else {
        newNode->dependents = NULL;
    }

    newNode->nextEmployee = NULL;
    return newNode;
}

2. 辅助函数：复制整个链表 #

基于单个节点的复制函数，实现完整链表的复制：

struct employee* copyLinkedList(const struct employee* head) {
    if (head == NULL) return NULL;

    struct employee* newHead = copyEmployeeNode(head);
    if (newHead == NULL) return NULL;

    struct employee* currentSrc = head->nextEmployee;
    struct employee* currentDest = newHead;

    while (currentSrc != NULL) {
        currentDest->nextEmployee = copyEmployeeNode(currentSrc);
        if (currentDest->nextEmployee == NULL) {
            // 复制失败，释放已分配的内存
            freeLinkedList(newHead);
            return NULL;
        }
        currentSrc = currentSrc->nextEmployee;
        currentDest = currentDest->nextEmployee;
    }

    return newHead;
}

3. 辅助函数：释放副本链表内存 #

打印完成后需要释放副本链表的所有内存，避免泄漏：

void freeLinkedList(struct employee* head) {
    struct employee* temp;
    while (head != NULL) {
        temp = head;
        head = head->nextEmployee;

        // 释放依赖项内存
        if (temp->numDependents > 0) {
            for (int i = 0; i < temp->numDependents; i++) {
                free(temp->dependents[i]);
            }
            free(temp->dependents);
        }

        free(temp);
    }
}

4. 修改后的sortEmployee函数 #

现在修改sortEmployee，先复制原链表，对副本排序打印，最后释放副本：

void sortEmployee(struct employee* head) {
    if (head == NULL) {
        printf("Error!\n");
        return;
    }

    // 1. 复制原链表
    struct employee* copyHead = copyLinkedList(head);
    if (copyHead == NULL) {
        printf("Failed to copy linked list!\n");
        return;
    }

    // 2. 对副本链表进行冒泡排序（原排序逻辑不变，仅操作副本）
    struct employee *current, *sorted, *previous;
    struct employee* newHead = copyHead;
    int swapped = 1;

    while (swapped) {
        swapped = 0;
        previous = NULL;
        current = newHead;

        while (current->nextEmployee != NULL) {
            sorted = current->nextEmployee;
            if (current->empId > sorted->empId) {
                current->nextEmployee = sorted->nextEmployee;
                sorted->nextEmployee = current;
                if (previous == NULL) {
                    newHead = sorted;
                } else {
                    previous->nextEmployee = sorted;
                }
                previous = sorted;
                swapped = 1;
            } else {
                previous = current;
                current = current->nextEmployee;
            }
        }
    }

    // 3. 打印排序后的副本
    printf("Employees sorted by Employee Id: \n");
    printLL(newHead);

    // 4. 释放副本链表的内存
    freeLinkedList(copyHead);
}

效果验证 #

修改后调用sortEmployee(head)，函数内部会打印正确的排序结果，而main中的原链表节点连接关系完全不变，后续调用printLL(head)会输出和初始状态完全一致的内容。

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