已知链表结构为：typedef struct Node{int data; struct Node *next;}Node;编写函数实现：合并两个有序链表，使之仍然有序。函数原型为：Node * merge(Node*h1,Node*h2);

实现代码如下：

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

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

Node* merge(Node* h1, Node* h2) {
    Node *p, *q, *r;
    p = h1;
    q = h2;
    r = (Node*)malloc(sizeof(Node));
    r->next = NULL;
    Node* t = r;
    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            t->next = p;
            t = p;
            p = p->next;
        } else {
            t->next = q;
            t = q;
            q = q->next;
        }
    }
    if (p == NULL) {
        t->next = q;
    } else {
        t->next = p;
    }
    return r->next;
}

int main() {
    Node *h1, *h2, *p1, *p2, *tmp;
    h1 = (Node*)malloc(sizeof(Node));
    h2 = (Node*)malloc(sizeof(Node));
    h1->data = 1;
    h2->data = 2;
    p1 = h1;
    p2 = h2;
    for (int i = 2; i <= 5; i++) {
        tmp = (Node*)malloc(sizeof(Node));
        tmp->data = i * 2 - 1;
        tmp->next = NULL;
        p1->next = tmp;
        p1 = tmp;
    }
    for (int i = 3; i <= 6; i++) {
        tmp = (Node*)malloc(sizeof(Node));
        tmp->data = i * 2;
        tmp->next = NULL;
        p2->next = tmp;
        p2 = tmp;
    }
    printf("List 1:\n");
    tmp = h1;
    while (tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    printf("\nList 2:\n");
    tmp = h2;
    while (tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    printf("\nAfter merge:\n");
    tmp = merge(h1, h2);
    while (tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    return 0;
}

运行结果为：

List 1:
1 3 5 7 9
List 2:
2 4 6 8 10
After merge:
1 2 3 4 5 6 7 8 9 10