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

struct Node {
    int data;
    struct Node *prev, *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) temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

struct Node* mergeLists(struct Node* head1, struct Node* head2) {
    struct Node* merged = NULL;
    while (head1 && head2) {
        if (head1->data <= head2->data) {
            append(&merged, head1->data);
            head1 = head1->next;
        } else {
            append(&merged, head2->data);
            head2 = head2->next;
        }
    }
    while (head1) {
        append(&merged, head1->data);
        head1 = head1->next;
    }
    while (head2) {
        append(&merged, head2->data);
        head2 = head2->next;
    }