C语言链表覆盖写入问题及代码内存释放疑问求助

Hey there! Let's break down your questions one by one and fix the issues in your code.

Looking at your code, the line free(sortedList); right after *pList = sortedList; is a major bug. Here's why:

• You just set the original list pointer (*pList) to point to your new sorted list. Freeing sortedList immediately deallocates that memory, leaving *pList as a dangling pointer (pointing to invalid memory). Accessing it later will cause undefined behavior.

1. How to "Overwrite" the Input Linked List #

To properly overwrite the input list, you need two key steps:

1. Free all nodes of the original list to avoid memory leaks (your code skipped this step).
2. Assign the head of your new sorted list to *pList (your line *pList = sortedList; was correct—you just messed up the order with the free call).

Since you're using a double pointer (Node **pList), modifying *pList directly updates the original pointer outside your function, which is exactly what you want for "overwriting".

2. free(sortedList) Behavior & Proper List Deallocation #

• free(sortedList) only frees the single node that sortedList points to—not the entire linked list. Each node in your list is a separate block of memory allocated with malloc, so you can't free the whole list in one go.
• Yes, you must traverse the list to free each node individually. Here's a helper function to do that:

void freeList(Node **pList) {
    Node *temp;
    while (*pList != NULL) {
        temp = *pList;          // Save current node
        *pList = (*pList)->pNext; // Move head to next node
        free(temp);             // Free the saved node
    }
}

3. Fixing Your Sorting Logic (Bonus!) #

Your insertFront call will build the sorted list in reverse order (since you're adding elements from the start of the sorted array to the front of the list). To fix this, either:

• Iterate the sorted array in reverse when calling insertFront, or
• Implement an insertEnd function to add elements to the tail of the new list.

Here's your function with all fixes applied, including memory cleanup and proper list overwriting:

// Helper function to free an entire linked list
void freeList(Node **pList) {
    Node *temp;
    while (*pList != NULL) {
        temp = *pList;
        *pList = (*pList)->pNext;
        free(temp);
    }
}

void sortPlaylist(Node **pList) {
    if (*pList == NULL) return; // Handle empty list edge case

    Node *pCur = *pList;
    int size = sizeOfList(*pList);

    // Allocate array to hold records (always check malloc success!)
    Record *records = malloc(size * sizeof(Record));
    if (records == NULL) {
        perror("malloc failed for records array");
        return;
    }

    // Copy records from original list to array
    for (int i = 0; i < size; i++) {
        records[i] = pCur->record;
        pCur = pCur->pNext;
    }

    // Selection sort the records (example sorting by artist name)
    for (int i = 0; i < size - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < size; j++) {
            if (strcmp(records[j].artist, records[minIdx].artist) < 0) {
                minIdx = j;
            }
        }
        // Swap records to place minimum in correct position
        Record temp = records[i];
        records[i] = records[minIdx];
        records[minIdx] = temp;
    }

    // Free the original list to avoid memory leaks
    freeList(pList);

    // Build sorted list (reverse array to use insertFront without order reversal)
    Node *sortedList = NULL;
    for (int i = size - 1; i >= 0; i--) {
        insertFront(&sortedList, records[i]);
    }

    // Overwrite the original list pointer with the sorted list
    *pList = sortedList;

    // Free the temporary records array
    free(records);
}

You mentioned your method is inefficient—and you're right! Copying to an array, sorting, and rebuilding the list has a time complexity of O(n²) (thanks to selection sort). If you want a faster approach later, look into merge sort for linked lists: it's O(n log n) time, can be implemented in-place, and avoids needing an extra array. But your current approach is totally valid for learning purposes!

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