合并单链表

发布于 25 天前  0 次阅读


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

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

void insertNode(SinglyLinkedNode **head_ref, int data);

void printLinkedList(SinglyLinkedNode *node);

void moveNode(SinglyLinkedNode **dest_ref, SinglyLinkedNode **src_ref);

SinglyLinkedNode *mergeSortedLinkedList(SinglyLinkedNode *la, SinglyLinkedNode *lb) {
    // 辅助结点,next 指针持有合并后的有序链表
    SinglyLinkedNode dummy;
    // 有序链表的尾结点
    SinglyLinkedNode *tail = &dummy;
    while (1) {
        // 如果有一个链表为空,直接与另一个链表接起来
        if (!la) {
            tail->next = lb;
            break;
        } else if (!lb) {
            tail->next = la;
            break;
        }
        // 将头结点较小的优先添加到 tail
        if (la->data <= lb->data) {
            moveNode(&(tail->next), &la);
        } else {
            moveNode(&(tail->next), &lb);
        }
        tail = tail->next;
    }
    return dummy.next;
}

// 将 src_ref 的头结点,添加到 dest_ref 的头部。
void moveNode(SinglyLinkedNode **dest_ref, SinglyLinkedNode **src_ref) {
    if (*src_ref == NULL) return;
    SinglyLinkedNode *new_node = *src_ref;
    *src_ref = new_node->next;
    new_node->next = *dest_ref;
    *dest_ref = new_node;
}

// 插入新结点到链表头部
void insertNode(SinglyLinkedNode **head_ref, int data) {
    SinglyLinkedNode *new_node = malloc(sizeof(SinglyLinkedNode));
    new_node->data = data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}

// 打印链表
void printLinkedList(SinglyLinkedNode *node) {
    printf("--- start ---\n");
    while (node) {
        printf("data: %d\n", node->data);
        node = node->next;
    }
    printf("--- end ---\n");
}

int main() {
    int n;
    scanf("%d", &n);
    SinglyLinkedNode *h1 = NULL, *h2 = NULL;
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        insertNode(&h1, a);
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int a;
        scanf("%d", &a);
        insertNode(&h2, a);
    }
    printLinkedList(mergeSortedLinkedList(h1, h2));
    return 0;
}