C++ 有序單向鏈表實作：插入正序、遞迴逆序列印

實作一個維持遞增序的單向鏈表，支援插入節點（自動排序）、正序列印、逆序列印。原程式碼逆序列印邏輯錯誤（嘗試就地反轉鏈表卻未正確處理頭節點），改用遞迴列印最簡潔且不破壞結構。

核心資料結構

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

有序插入函式

void insert(Node*& head, int num) {
    Node* s = new Node{num, nullptr};
    if (!head || head->data > num) { // 插入頭部
        s->next = head;
        head = s;
        return;
    }
    Node *q = head, *p = head->next;
    for (; p; q = p, p = p->next) {
        if (p->data > num) { // 找到插入位置
            s->next = p;
            q->next = s;
            return;
        }
    }
    q->next = s; // 插入尾部
}

正序列印

void show(Node* head) {
    cout << "List: ";
    for (; head; head = head->next) cout << head->data << ' ';
    cout << endl;
}

逆序列印：遞迴法（推薦）

void reversePrint(Node* head) {
    if (!head) return;
    reversePrint(head->next);
    cout << head->data << ' ';
}
// 呼叫
cout << "Reverse: ";
reversePrint(head);
cout << endl;

遞迴利用呼叫堆疊天然實現逆序，程式碼極簡、不修改鏈表、無記憶體洩漏風險。若資料量極大（>10^5）需改用棧模擬避免堆疊溢位。

主程式測試

int main() {
    Node* head = nullptr;
    for (int k = 1; k <= 5; ++k) insert(head, k); // 1 2 3 4 5
    show(head);       // 1 2 3 4 5
    reversePrint(head); // 5 4 3 2 1
    // 記得釋放記憶體...
}

掌握「雙指針尋找插入點」與「遞迴逆序列印」兩大核心模式，單向鏈表基本操作即可靈活駕馭。