單鏈表常用操作全集：創建、插入、刪除、排序、逆置、打印

節點定義

Node* Create() {
    Node *head = new Node(), *tail = head;
    int x;
    cout << "Input elements (0 to end): ";
    while (cin >> x && x != 0) {
        Node* n = new Node{x, nullptr};
        tail->next = n;
        tail = n;
    }
    Node* realHead = head->next;
    delete head; // 釋放哨兵頭節點
    return realHead;
}

2. 求長度

Node* Insert(Node* head, int val) {
    Node* n = new Node{val, nullptr};
    if (!head || val <= head->data) {
        n->next = head;
        return n;
    }
    Node* p = head;
    while (p->next && p->next->data < val) p = p->next;
    n->next = p->next;
    p->next = n;
    return head;
}

4. 刪除指定值（首次出現）

5. 逆置（迭代三指針法）
Node* Sort(Node* head) {
    int n = Length(head);
    for (int i = 0; i < n-1; i++) {
        Node* p = head;
        for (int j = 0; j < n-1-i; j++) {
            if (p->data > p->next->data) swap(p->data, p->next->data);
            p = p->next;
        }
    }
    return head;
}


7. 打印
next) cout << p->data << ' ';
    cout << endl;
}


主程序測試
操作時間空間
創建/打印/長度O(N)O(1)
插入/刪除/查找O(N)O(1)
逆置O(N)O(1)
冒泡排序O(N²)O(1)

生產代碼排序優先用合併排序 O(N log N) 或轉 vector 排序後重建。