Merge two sorted lists – Data Structures Practice

Join two sorted linked lists into one sorted list without creating any new nodes.

What to build

A merge function that relinks the nodes of two sorted lists into one.

Requirements

Do not allocate new nodes or copy values: change only the next pointers.
When two values are equal, take the one from the first list first.
Print the merged list, or empty if both lists are empty.

Input

A line with n and a line with n numbers in increasing order, then a line with m and a line with m numbers in increasing order. A list with no numbers has an empty line.

Output

The merged numbers on one line, separated by spaces, or empty.

Constraints

0 ≤ n, m ≤ 100.

Example

Input:

Output:

1 2 4 5 9

Why it works

The smallest remaining value is always at the front of one of the two lists, so comparing just the two front nodes is enough. Each node is relinked once, which makes the merge O(n + m).

Examples

Example 1 · Input

Expected output

1 2 4 5 9

Example 2 · Input

Expected output

3 3 3 8

Hints

Hint 1

Keep a head and a tail for the merged list, as you do when appending.

Hint 2

While both lists have nodes, take the smaller front node and move that list on by one.

Hint 3

When one list runs out, link the whole of the other list after the tail.

Solution

Show one correct solution (try it yourself first)

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

typedef struct node {
    int value;
    struct node *next;
} Node;

Node *read_list(void) {
    int n;
    scanf("%d", &n);
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *p = malloc(sizeof(Node));
        scanf("%d", &p->value);
        p->next = NULL;
        if (head == NULL) head = p;
        else tail->next = p;
        tail = p;
    }
    return head;
}

Node *merge(Node *a, Node *b) {
    Node *head = NULL, *tail = NULL;
    while (a != NULL && b != NULL) {
        Node *pick;
        if (a->value <= b->value) {
            pick = a;
            a = a->next;
        } else {
            pick = b;
            b = b->next;
        }
        if (head == NULL) head = pick;
        else tail->next = pick;
        tail = pick;
    }
    Node *rest = a != NULL ? a : b;
    if (head == NULL) head = rest;
    else tail->next = rest;
    return head;
}

int main(void) {
    Node *a = read_list();
    Node *b = read_list();
    Node *head = merge(a, b);
    if (head == NULL) printf("empty");
    for (Node *p = head; p != NULL; p = p->next) {
        if (p != head) printf(" ");
        printf("%d", p->value);
    }
    printf("\n");
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
    return 0;
}

Lesson: Singly linked lists →