C 语言实现两个有序单链表的合并与插入操作

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

// 定义链表节点结构 struct Node { int data; struct Node* next; };

// 尾插法建立有序链表 A void buildListA(struct Node** headA, int lengthA) { int i; struct Node* tail = headA; for (i = 0; i < lengthA; i++) { int data; scanf('%d', &data); struct Node newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL;

    if (*headA == NULL) {
        *headA = newNode;
        tail = newNode;
    } else {
        tail->next = newNode;
        tail = newNode;
    }  
}

}

// 头插法建立有序链表 B void buildListB(struct Node** headB, int lengthB) { int i; struct Node* head = headB; for (i = 0; i < lengthB; i++) { int data; scanf('%d', &data); struct Node newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data;

    if (*headB == NULL || data < (*headB)->data) {
        newNode->next = *headB;
        *headB = newNode;
    } else {
        struct Node* current = *headB;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

}

// 合并链表 A 和 B 为 C，并去重 struct Node* mergeLists(struct Node* headA, struct Node* headB) { struct Node* headC = headA; struct Node* tailC = headA; struct Node* currentA = headA->next; struct Node* currentB = headB;

while (currentA != NULL && currentB != NULL) {
    if (currentA->data < currentB->data) {
        tailC->next = currentA;
        tailC = currentA;
        currentA = currentA->next;
    } else if (currentA->data > currentB->data) {
        tailC->next = currentB;
        tailC = currentB;
        currentB = currentB->next;
    } else {
        currentA = currentA->next;
    }
}

if (currentA != NULL) {
    tailC->next = currentA;
} else {
    tailC->next = currentB;
}

return headC;

}

// 在链表 C 中插入新元素 item void insertElement(struct Node** headC, int item) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = item; newNode->next = NULL;

if (*headC == NULL || item < (*headC)->data) {
    newNode->next = *headC;
    *headC = newNode;
} else {
    struct Node* current = *headC;
    while (current->next != NULL && current->next->data < item) {
        current = current->next;
    }
    if (current->next == NULL || current->next->data > item) {
        newNode->next = current->next;
        current->next = newNode;
    }
}

}

// 打印链表 void printList(struct Node* head) { struct Node* current = head; while (current != NULL) { printf('%d ', current->data); current = current->next; } printf(' '); }

int main() { int lengthA, lengthB, item; struct Node* headA = NULL; struct Node* headB = NULL;

// 输入 A 表的长度和数据元素
scanf('%d', &lengthA);
buildListA(&headA, lengthA);

// 输入 B 表的长度和数据元素
scanf('%d', &lengthB);
buildListB(&headB, lengthB);

// 输入要插入的新元素 item
scanf('%d', &item);

struct Node* headC = mergeLists(headA, headB);
insertElement(&headC, item);
printList(headC);

return 0;

}