How to merge two linked lists in C

Question

I am given two sorted linked lists in C, and I am trying to merge them together, so that they will be in sorted order. Can anyone tell me why my code doesn't work.

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {

    struct ListNode *node;

    node = NULL;

    struct ListNode *n = (struct ListNode *)malloc(sizeof(struct ListNode));

    node = n;

    while (l1 != NULL && l2 != NULL) {
        if ((*l1).val < (*l2).val) {
            (*n).val = (*l1).val;
            l1 = (*l1).next;
        } else {
            (*n).val = (*l2).val;
            l2 = (*l2).next;
        }
        (*n).next = (struct ListNode *)malloc(sizeof(struct ListNode));
        n = (*n).next;
    }
    if (l1 != NULL) {
        n = l1;
    }
    if (l2 != NULL) {
        n = l2;
    }
    return node;
}

Answer 1

Instead of merging the 2 lists, you are just creating a new list, copying values from both lists in increasing order, but you fail to copy the remaining elements when one if the lists is exhausted.

Note these extra remarks:

• you are probably expected to merge the lists in place and return a pointer to the head of the merged list.
• the syntax (*l1).val is not strictly incorrect in C, but the pointer syntax l1->val is considered much more readable.

Here is a modified version:

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
    struct ListNode *head, *n;

    n = head = NULL;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            if (n == NULL) {
                n = head = l1;
            } else {
                n = n->next = l1;
            }
            l1 = l1->next;
        } else {
            if (n == NULL) {
                n = head = l2;
            } else {
                n = n->next = l2;
            }
            l2 = l2->next;
        }
    }                
    if (l1 != NULL) {
        if (n == NULL) {
            head = l1;
        } else {
            n->next = l1;
        }
    } else {
        if (n == NULL) {
            head = l2;
        } else {
            n->next = l2;
        }
    }
    return head;
}

Answer 2

• First, decide if you want to merge the original lists, or you want to return a copy of the list(but with the same values)
• if you want a copy, there should be exactly one malloc() for every input node you pass. (you can verify that in the merge loop, either l1 or l2 is advanced, and one node is (possibly) allocated)

---

#include <stdio.h>

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

#if WANT_CLONE
#include <stdlib.h>
struct node *clone(struct node *p)
{
struct node *q;
if (!p) return NULL;
q = malloc (sizeof *q);
*q = *p;
return q;
}

#define CLONE(x) clone(x)
#else
#define CLONE(x) (x)
#endif

struct node *merge(struct node *l1, struct node *l2)
{
struct node dummy = {NULL,0}, *here;

for(here = &dummy; l1 || l2; here = here->next) {
        if (!l2 || l1 && l1->val <= l2->val) {
                here->next= CLONE(l1); l1 = l1->next;
                }
        else    if(!l1 || l2) {
                here->next= CLONE(l2); l2 = l2->next;
                }
        }

return dummy.next;
}

        /* Some test data */
struct node evens[] = {
{evens+1, 0}, {evens+2, 2}, {evens+3, 4}, {evens+4, 6}, {NULL, 8}, };

struct node odds[] = {
{odds+1, 1}, {odds+2, 3}, {odds+3, 5}, {odds+4, 7}, {odds+5, 9}, {NULL, 11}, };

void print(struct node *p)
{
for( ; p; p = p->next) {
        printf(" %d", p->val);
        }
printf("\n");
}

int main(void)
{
struct node *both;

printf("odds:"); print(odds);
printf("evens:"); print(evens);
both = merge(odds, evens);
printf("both:"); print(both);

printf("odds:"); print(odds);
printf("evens:"); print(evens);

return 0;
}