九度 OJ 1518：鏈表反轉——後插法構建與頭插法反轉

問題描述

輸入鏈表長度 n (0 ≤ n ≤ 1000) 及 n 個節點值，反轉鏈表並輸出。多測試用例至 EOF。n=0 輸出 NULL。必須使用鏈表結構實現。

算法設計

1. 尾插法建表：維護尾指針 tail，新節點接在尾部，O(n) 建表。
2. 頭插法反轉：從第二個節點開始，依次將當前節點摘下，插入到頭結點之後。過程：

初始: head -> 1 -> 2 -> 3 -> 4 -> 5
步驟1: 取 2, head -> 2 -> 1 -> 3 -> 4 -> 5
步驟2: 取 3, head -> 3 -> 2 -> 1 -> 4 -> 5
...
最終: head -> 5 -> 4 -> 3 -> 2 -> 1

只需一個 prev 指向已反轉部分最後一個節點，curr 指向待處理節點，迭代調整指針。

C++ 完整代碼

#include 
#include 
using namespace std;

struct LNode {
    int data;
    LNode* next;
    LNode(int v=0): data(v), next(nullptr) {}
};

LNode* createList(int n) {
    LNode* head = new LNode(); // 哑節點
    LNode* tail = head;
    for (int i = 0; i < n; ++i) {
        int val; cin >> val;
        tail->next = new LNode(val);
        tail = tail->next;
    }
    return head;
}

LNode* reverseList(LNode* head) {
    LNode* prev = head->next; // 第一個節點作為已反轉部分尾部
    if (!prev) return head;
    LNode* curr = prev->next;
    prev->next = nullptr; // 斷開，已反轉部分結尾
    while (curr) {
        LNode* next = curr->next;
        curr->next = head->next; // 插到頭結點後
        head->next = curr;
        curr = next;
    }
    return head;
}

void printList(LNode* head) {
    LNode* p = head->next;
    if (!p) { cout << "NULL\n"; return; }
    cout << p->data;
    p = p->next;
    while (p) { cout << ' ' << p->data; p = p->next; }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        if (n == 0) { cout << "NULL\n"; continue; }
        LNode* head = createList(n);
        head = reverseList(head);
        printList(head);
        // 釋放內存（OJ 通常不強求，但好習慣）
        LNode* p = head;
        while (p) { LNode* t = p; p = p->next; delete t; }
    }
    return 0;
}

關鍵點解析

• 哑節點：簡化頭結點特殊情況處理（插入、刪除、反轉統一邏輯）。
• 頭插法反轉：時間 O(n)，空間 O(1)，單次遍歷完成。遞歸反轉雖簡潔但棧深度 O(n) 可能溢出。
• 輸入輸出優化：ios::sync_with_stdio(false); cin.tie(nullptr); 加速大量輸入。
• 內存釋放：雖然程序結束系統回收，但面試/OJ 環境建議顯式釋放。

總結

九度 1518 是鏈表基本操作的綜合考查：尾插建表 + 頭插反轉 + 遍歷輸出。掌握哑節點技巧與指針操作不變量（如反轉時保持「已反轉部分」與「待處理部分」分離），是鏈表題目的核心功夫。