C 語言實作：兩無序單向鏈表排序合併為有序鏈表

本文示範如何在 C 語言中將兩個無序單向鏈表，先分別排序，再合併為一個遞增有序鏈表。演算法採用氣泡排序法對鏈表原地排序，再以雙指針合併，最後反轉鏈表以獲得正確順序。

資料結構定義

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

演算法流程

1. 建立鏈表：動態分配節點，以 999 為哨兵結束輸入。
2. 氣泡排序：對兩個鏈表分別進行原地氣泡排序 (O(n²))，交換節點 data 欄位。
3. 合併有序鏈表：雙指針遍歷兩已排序鏈表，將較小節點插入新鏈表頭部 (此時新鏈表為遞減序)。
4. 反轉鏈表：將合併後的遞減鏈表反轉，得到最終遞增有序鏈表。

完整程式碼

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

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

void bubbleSort(struct Node *head, int count) {
    for (int i = 0; i < count - 1; ++i) {
        for (struct Node *p = head->next; p->next != NULL; p = p->next) {
            if (p->data > p->next->data) {
                int tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
            }
        }
    }
}

void printList(struct Node *head) {
    for (struct Node *p = head->next; p; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

int main() {
    struct Node *head1 = malloc(sizeof(struct Node));
    struct Node *head2 = malloc(sizeof(struct Node));
    head1->next = head2->next = NULL;
    int count1 = 0, count2 = 0;

    // 輸入鏈表 1
    printf("輸入鏈表1數據 (999結束):\n");
    int val;
    while (scanf("%d", &val), val != 999) {
        struct Node *node = malloc(sizeof(struct Node));
        node->data = val;
        node->next = head1->next;
        head1->next = node;
        count1++;
    }

    // 輸入鏈表 2
    printf("輸入鏈表2數據 (999結束):\n");
    while (scanf("%d", &val), val != 999) {
        struct Node *node = malloc(sizeof(struct Node));
        node->data = val;
        node->next = head2->next;
        head2->next = node;
        count2++;
    }

    // 排序
    bubbleSort(head1, count1);
    bubbleSort(head2, count2);
    printf("鏈表1排序後: "); printList(head1);
    printf("鏈表2排序後: "); printList(head2);

    // 合併 (頭插法產生遞減序)
    struct Node *head3 = malloc(sizeof(struct Node));
    head3->next = NULL;
    struct Node *p1 = head1->next, *p2 = head2->next;
    while (p1 && p2) {
        struct Node *next;
        if (p1->data <= p2->data) {
            next = p1->next;
            p1->next = head3->next;
            head3->next = p1;
            p1 = next;
        } else {
            next = p2->next;
            p2->next = head3->next;
            head3->next = p2;
            p2 = next;
        }
    }
    while (p1) { struct Node *n = p1->next; p1->next = head3->next; head3->next = p1; p1 = n; }
    while (p2) { struct Node *n = p2->next; p2->next = head3->next; head3->next = p2; p2 = n; }

    // 反轉得到遞增序
    struct Node *cur = head3->next;
    head3->next = NULL;
    while (cur) {
        struct Node *n = cur->next;
        cur->next = head3->next;
        head3->next = cur;
        cur = n;
    }

    printf("合併後有序鏈表: "); printList(head3);
    return 0;
}

執行結果示例

補充說明

• 氣泡排序僅適合教學或小規模資料；實務上大型鏈表排序建議使用歸併排序 (O(n log n))。
• 合併時採用頭插法再反轉，避免了維護尾指針的麻煩，程式碼較簡潔。
• 記得在程式結束前釋放所有 malloc 分配的記憶體，避免洩漏。