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

struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

void append(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

struct Node* mergeLists(struct Node* head1, struct Node* head2) {
    struct Node* merged = NULL;
    struct Node* p1 = head1;
    struct Node* p2 = head2;

    while (p1 && p2) {
        if (p1->data <= p2->data) {
            append(&merged, p1->data);
            p1 = p1->next;
        } else {
            append(&merged, p2->data);
            p2 = p2->next;
        }
    }

    while (p1) {
        append(&merged, p1->data);
        p1 = p1->next;
    }
    while (p2) {
        append(&merged, p2->data);
        p2 = p2->next;
    }

    return merged;
}