Trouble merging two linked lists in C

Question

I am supposed to write a function to merge (put one at the end of another) two singly linked lists. The user inputs a series of numbers into the console, for example: 1 2 3 4 0 (0 signifies the end of input and is not an element of the list). These numbers are put into the linked list, the list now looks like this: 1 2 3 4. The process repeats again until we have two different linked lists. Then the merging function is called "void merge(struct Node head1, struct Node head2)". Programs ends after the new list is printed.

My thought process would be to first have my pointer point at the end of the first list, then just make a while loop that will go through the other list and make the next element of the first list the current element of the second list.

typedef struct Element Element;

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

Element *addNew(int data)
{
    Element *newN = (Element*)malloc(sizeof(Element));

    newN->data = data;
    newN->next = NULL;

    return newN;
}

Element *add_on_beginning(Element *head, Element *newN)
{
    newN->next = head;

    return newN;
}

Element *add_on_end(Element *head, Element *newN)
{
    if(head == NULL)
    {
        return newN;
    }

    Element *temp = head;

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

    temp->next = newN;

    return head;
}

void printElement(Element *element)
{
    printf("%d ", element->data);
}

void printList(Element *head)
{
    Element *temp = head;

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

void merge(Element *head1, Element *head2)
{
    Element *temp1 = head1;
    Element *temp2 = head2;

    while(temp1->next != NULL)
    {
        temp1 = temp1->next;
    }

    while(temp2->next != NULL)
    {
        temp1->next = temp2;
        temp2 = temp2->next;
    }
}

int main()
{
    Element *head1 = NULL;
    Element *head2 = NULL;

    int arr[1000];
    char temp1;
    char temp2;
    int i = 0;
    int j = 0;

    printf("Input the first set of elements: \n");

    while(temp1 != '\n')
    {
        scanf("%d%c", &arr[i], &temp1);

        if(arr[i] == 0)
        {
            break;
        }

        head1 = add_on_end(head1, addNew(arr[i]));

        i++;
    }

    printf("Input the second set of elements: \n");

    while(temp2 != '\n')
    {
        scanf("%d%c", &arr[j], &temp2);

        if(arr[j] == 0)
        {
            break;
        }

        head2 = add_on_end(head2, addNew(arr[j]));

        j++;
    }

    merge(head1, head2);

    printList(head1);

    return 0;
}

So for some reason, the function only reads last two elements of the second list.

INPUT:

1 2 3 4 0
5 6 7 8 0

OUTPUT:

1 2 3 4 7 8

The result I'm supposed to get is

INPUT:

1 2 3 4 0
5 6 7 8 0

OUTPUT:

1 2 3 4 5 6 7 8

Not your problem, but I suggest sticking with simpler invocations of scanf. Don't bother with %c and seeing if there was a newline. But do check scanf's return value, and only proceed it it's 1. — Steve Summit
You want to make the next element at the end of the first list point at the head of the second list. In merge(), there's no need to scan the second list at all. — Steve Summit
That actually worked, I can't believe I was so stupid not to see that...So for anyone that's looking at this post in the future, in the function merge, just get rid of the second while loop and instead write temp->next = head2, thats all. @SteveSummit thanks for all the help! — igor
As written, your merge function can't handle the case that the first list is NULL. To handle that (and in keeping with the way your other functions, like add_on_end, are written), you'd want to have merge return the new list. — Steve Summit
While the description of tag merge is generic enough, I'd avoid the term merge for a union of data structures without O(1) "random"/indexed access if it was not keeping the order each of the structures shows individually. join, chain, concatenate, (unite?), … — greybeard

Vlad from Moscow Vlad from Moscow · Accepted Answer · 2019-08-23T17:50:54

This function

void merge(Element *head1, Element *head2)
{
    Element *temp1 = head1;
    Element *temp2 = head2;

    while(temp1->next != NULL)
    {
        temp1 = temp1->next;
    }

    while(temp2->next != NULL)
    {
        temp1->next = temp2;
        temp2 = temp2->next;
    }
}

is invalid.

First of all it does not change the original pointers head1 and head2 because they are passed to the function by value. So the function deals with copies of the original pointers.

Secondly in the function there is no check whether head1 or head2 is equal to NULL.

The function can be defined the following way

void merge( Element **head1, Element **head2 )
{
    if ( *head1 == NULL )
    {
        *head1 = *head2;
        *head2 = NULL;
    }
    else if ( *head2 != NULL )
    {
        while ( *head1 != NULL ) head1 = &( *head1 )->next;

        for ( ; *head2 != NULL; head2 = &( *head2 )->next )
        {
            *head1 = *head2;
            head1 = &( *head1 )->next;
        }
    }              
}

Pay attention to that there is no need to declare an array to input data in the list.

Also these while loops

    char temp1;
    char temp2;
    int i = 0;
    int j = 0;

    printf("Input the first set of elements: \n");

    while(temp1 != '\n')
    //..

and

   while(temp2 != '\n')
   //...

has undefined behavior because neither temp1 nor temp2 are initialized.

Trouble merging two linked lists in C

2 Answers