Duplicating a linked list without using recursion-CodePudding

I'm trying to figure out how to duplicate a linked list, and after debugging on Vs code I'm getting a segmentation fault on cuurent->data = temp->data; and I'm not sure why this is happening.

and this is the code:

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

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

struct node* Insert(struct node* head, int x)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = x;
    temp->next = head;
    return temp;
}

void Print(struct node* head)
{
    struct node* tmp1 = head;
    printf("List is:");
    while (tmp1 != NULL) {
        printf(" %d", tmp1->data);
        tmp1 = tmp1->next;
    }
    printf("\n");
}

struct node* dupe(struct node* head, struct node* head2)
{
    if (head == NULL)
        return NULL;
    struct node* temp = head;
    struct node* prev = NULL;
    struct node* cuurent = (struct node*)malloc(sizeof(struct node));
    cuurent->data = temp->data;
    if (head2 == NULL) {
        cuurent->next = head2;
        head2 = cuurent;
    }
    while (temp != NULL) {
        temp = temp->next;
        cuurent = (struct node*)malloc(sizeof(struct node));
        cuurent->data = temp->data;
        cuurent->next = prev;
        prev = cuurent;
    }
    return head2;
}

int main(void)
{
    head = NULL;
    head2 = NULL;
    head = Insert(head, 4);
    head = Insert(head, 2);
    head = Insert(head, 3);
    head = Insert(head, 5);
    head2 = dupe(head, head2);
    Print(head);
    Print(head2);
}

CodePudding user response：

As pointed out in the comments,

while (temp != NULL) {
    temp = temp->next;

changes the value of temp immediately after guarding against a null pointer value.

This eventually means

cuurent->data = temp->data;

will cause Undefined Behaviour by dereferencing temp when it is the null pointer value.

You can apply the exact same looping principles shown in Print to copy the list. The only difference being you must save a pointer to the first node.

The same principle can be used again when it comes time to free the memory.

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

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

struct node *insert(struct node *next, int x)
{
    struct node *n = malloc(sizeof *n);

    n->data = x;
    n->next = next;

    return n;
}

void print_list(struct node *head)
{
    printf("List is: ");

    while (head) {
        printf("%d ", head->data);
        head = head->next;
    }

    printf("\n");
}

void free_list(struct node *head)
{
    struct node *t;

    while (head) {
        t = head->next;
        free(head);
        head = t;
    }
}

struct node *copy_list(struct node *head)
{
    struct node *root = NULL;

    for (struct node *current; head; head = head->next) {
        struct node *new = insert(NULL, head->data);

        if (!root)
            root = new;
        else
            current->next = new;

        current = new;
    }

    return root;
}

int main(void)
{
    struct node *head = NULL;
    head = insert(head, 4);
    head = insert(head, 2);
    head = insert(head, 3);
    head = insert(head, 5);

    struct node *head2 = copy_list(head);

    print_list(head);
    print_list(head2);

    free_list(head);
    free_list(head2);
}

Output:

List is: 5 3 2 4 
List is: 5 3 2 4