如何在C语言中复制链表至新地址并动态追加元素？

Got it, let's tackle this copyPath function step by step. The core goal is to create a fully independent copy of the input linked list, then append the specified integer to the end of this new copy—with each function call producing a standalone list that doesn't interfere with others.

Key Requirements Recap #

• Generate a deep copy of the original linked list (each node lives in new memory)
• Append the given node value to the end of the copied list
• Each call returns a fresh, independent list (so we can't rely on the global pathHead/pathTail variables—they'd get overwritten across calls)

Step-by-Step Implementation #

First, we'll use local pointers to track the head and tail of our new copied list. This ensures each call's list is isolated.

1. Initialize Local List Pointers #

Inside the function, declare variables to hold the new list's head and tail:

struct path *newHead = NULL;
struct path *newTail = NULL;

2. Copy the Original Linked List #

We'll traverse the original list from head to NULL, creating a new node for each element and adding it to our new list:

struct path *current = head;
while (current != NULL) {
    // Allocate memory for the copied node
    struct path *copyNode = malloc(sizeof(struct path));
    if (!copyNode) {
        // Handle malloc failure: clean up already allocated nodes to avoid leaks
        perror("Failed to allocate memory for copied node");
        struct path *temp = newHead;
        while (temp != NULL) {
            struct path *next = temp->next;
            free(temp);
            temp = next;
        }
        return NULL;
    }
    // Copy the node value and initialize next pointer
    copyNode->node = current->node;
    copyNode->next = NULL;

    // Add the copied node to the new list
    if (newHead == NULL) {
        newHead = copyNode;
        newTail = newHead;
    } else {
        newTail->next = copyNode;
        newTail = copyNode;
    }

    current = current->next;
}

3. Append the New Node #

Now we'll add the specified node value to the end of our copied list, using logic similar to newPathElement but with our local pointers:

// Allocate memory for the new node to append
struct path *newNode = malloc(sizeof(struct path));
if (!newNode) {
    // Clean up on failure
    perror("Failed to allocate memory for new node");
    struct path *temp = newHead;
    while (temp != NULL) {
        struct path *next = temp->next;
        free(temp);
        temp = next;
    }
    return NULL;
}
newNode->node = node;
newNode->next = NULL;

// Add to the end of the copied list
if (newHead == NULL) {
    // Original list was empty—new node becomes the entire list
    newHead = newNode;
    newTail = newNode;
} else {
    newTail->next = newNode;
    newTail = newNode;
}

4. Return the New List's Head #

Finally, return the head of our newly created and extended list:

return newHead;

Full Complete Code #

Putting it all together, here's the full copyPath function:

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

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

// Your existing global variables and newPathElement function (for context)
struct path *pathHead = NULL;
struct path *pathTail = NULL;
void newPathElement(int node) {
    struct path *rv = malloc(sizeof (struct path));
    rv->node = node;
    if (pathHead == NULL) {
        pathHead = rv;
        pathHead -> next = NULL;
        pathTail = pathHead;
    } else {
        pathTail -> next = rv;
        pathTail = rv;
        pathTail -> next = NULL;
    }
}

// The implemented copyPath function
struct path *copyPath(struct path *head, struct path *tail, int node){
    struct path *newHead = NULL;
    struct path *newTail = NULL;

    // Copy the original list
    struct path *current = head;
    while (current != NULL) {
        struct path *copyNode = malloc(sizeof(struct path));
        if (!copyNode) {
            perror("malloc failed for copy node");
            // Clean up allocated memory
            struct path *temp = newHead;
            while (temp != NULL) {
                struct path *next = temp->next;
                free(temp);
                temp = next;
            }
            return NULL;
        }
        copyNode->node = current->node;
        copyNode->next = NULL;

        if (newHead == NULL) {
            newHead = copyNode;
            newTail = newHead;
        } else {
            newTail->next = copyNode;
            newTail = copyNode;
        }

        current = current->next;
    }

    // Append the new node
    struct path *newNode = malloc(sizeof(struct path));
    if (!newNode) {
        perror("malloc failed for new node");
        // Clean up allocated memory
        struct path *temp = newHead;
        while (temp != NULL) {
            struct path *next = temp->next;
            free(temp);
            temp = next;
        }
        return NULL;
    }
    newNode->node = node;
    newNode->next = NULL;

    if (newHead == NULL) {
        newHead = newNode;
        newTail = newNode;
    } else {
        newTail->next = newNode;
        newTail = newNode;
    }

    return newHead;
}

Important Notes #

• Independence: By using local newHead and newTail instead of the global variables, every call to copyPath generates a completely separate list. You can store the returned head pointers in different variables to manage multiple lists.
• Memory Safety: We added cleanup logic for malloc failures to prevent memory leaks. This is a best practice—if allocation fails halfway through copying, we free all nodes we already created before returning.
• Edge Cases: The function handles empty input lists (where head is NULL) correctly—it will create a new list containing only the specified node value.

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