My function to merge two linked lists is not working properly

Question

I'm supposed to make a function that will merge two sorted singly linked lists.

The user inputs two sets of numbers in the console, for example: 5 3 1 0, which make a linked list, 0 signifies the end of that input and is not a part of that list. Then the lists are sorted, from the smallest to the largest value. After the sorting, elements of the lists are supposed to be added into a new list, one by one. At the end, the newly created list should be printed.

I've tried with a lot of different methods, but the one I liked the most was to have two different pointers to the heads, so p would be a pointer for head1 and q would be a pointer for head2. I start with whichever head value is smaller and move the pointer of that head to the next element. Then I remember that head with the node I'm going to return at the end, and move onto the while loop, where it goes from one list to another.

Okay, I use S to add the elements to my new list, first I start from the lower number between thew two lists, which is in this case 1 and the first list, as soon as I give S its value, I also move pointer p0 to the next element, so now its pointing to 3 (p1). Then I make that S the head of my new list and move onto the while loop. In while loop I check if the last element that was added to my new list was from the first or the second list, depending on the result, let's just say the last element was from the first list (number 1), we move onto the second list. I make S point to q1, q then points to the next element of the second list (q2) and the while loop starts again. The process repeats itself until one of the two pointers is NULL. After the while loop, I have two if statements (one for each pointers in case they point to NULL) where I return the other pointer. Hopefully now it's a bit more clear.

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 swap(Element *a, Element *b) {
    int tempV;

    tempV = a->data;
    a->data = b->data;
    b->data = tempV;
}

void sortList(Element *head) {
    Element *temp;
    int swapped;

    do {
        swapped = 0;

        temp = head;

        while (temp->next != NULL) {
            if (temp->data > temp->next->data) {
                swap(temp, temp->next);
                swapped = 1;
            }
            temp = temp->next;
        }
    } while(swapped);
}

Element *merge(Element *head1, Element *head2, Element *newHead) {
    Element *p = head1;
    Element *q = head2;
    Element *sort = NULL;

    if (p == NULL) {
        return q;
    }
    if (q == NULL) {
        return p;
    }

    if (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            sort = p;
            p = sort->next;
        } else {
            sort = q;
            q = sort->next;
        }
    }

    newHead = sort;

    while (p != NULL && q != NULL) {
        if (sort->next == p->next) {
            sort->next = q;
            sort = q;
            q = sort->next;
        } else {
            sort->next = p;
            sort = p;
            p = sort->next;
        }
    }

    if (p == NULL) {
        sort->next = q;
    }
    if (q == NULL) {
        sort->next = p;
    }

    return newHead;
}

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

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

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

int main() {
    Element *head = NULL;
    Element *head2 = NULL;
    Element *head3 = NULL;

    char t;
    int i;
    char p;
    int j;

    printf("Input the first set of numbers: 
");

    while (t != '
') {
        scanf("%d%c", &i, &t);

        if (i == 0) {
            break;
        }

        head = add_on_end(head, addNew(i));
    }

    printf("Input the second set of numbers: 
");

    while (p != '
') {
        scanf("%d%c", &j, &p);

        if (j == 0) {
            break;
        }

        head2 = add_on_end(head2, addNew(j));
    }

    sortList(head);
    sortList(head2);

    head3 = merge(head, head2, head3);

    printList(head3);

    return 0;
}

The problem I'm having is with merging, it prints out those two lists sorted but not merged with one and other, instead its the first list and right after the second.

So for example:

INPUT:

2 6 4 8 1 
7 9 2 3 5

OUTPUT:

1 2 4 6 8 2 3 5 7 9

It should be:

INPUT:

2 6 4 8 1
7 9 2 3 5

OUTPUT:

1 2 2 3 4 5 6 7 8 9

chqrlie · Accepted Answer

The merge function is too complicated:

the test if (p != NULL && q != NULL) is redundant
in the while loop you do not test the node values, which explains why merge fails.
the third argument newHead is useless.

Here is a modified version:

Element *merge(Element *p, Element *q) {
    Element *newHead = NULL;
    Element *sort = NULL;

    if (p == NULL) {
        return q;
    }
    if (q == NULL) {
        return p;
    }

    if (p->data <= q->data) {
        newHead = sort = p;
        p = p->next;
    } else {
        newHead = sort = q;
        q = q->next;
    }

    while (p != NULL && q != NULL) {
        if (p->data <= q->data) {
            sort = sort->next = p;
            p = p->next;
        } else {
            sort = sort->next = q;
            q = q->next;
        }
    }
    if (p == NULL) {
        sort->next = q;
    }
    if (q == NULL) {
        sort->next = p;
    }
    return newHead;
}

My function to merge two linked lists is not working properly

Answers (2)

Related Questions