C 語言實現鏈表每 K 個節點反轉（PAT 經典題）

題目大意

給定單鏈表頭結點地址、節點總數 N (≤ 10^5)、反轉長度 K (≤ N)。每 K 個節點為一組進行鏈接反轉，不足 K 者保持原序。輸出反轉後的鏈表，每行格式：Address Data Next。

數據結構設計

struct Node {
    int addr;   // 5位地址
    int data;   // 數據值
    int next;   // 下一節點地址
    int order;  // 原始鏈表中的序號（用於排序）
} nodes[100000];

算法步驟

1. 讀入並構建地址映射：用 addr → index 數組/哈希表，O(1) 定位節點。
2. 遍歷鏈表賦予序號：從頭結點出發，按 next 串聯，給每個節點打上 order = 0,1,2...。未被訪問到的節點（孤立節點）order = -1，後續忽略。
3. 按 order 排序：將有效節點按 order 升序排列，得到邏輯順序數組 valid[]。
4. 分組反轉：對 valid 每 K 個元素調用 reverse，最後一組不足 K 不動。
5. 重建 next 指針並輸出：按新順序串聯 next，最後一個指向 -1，按格式打印。

關鍵代碼片段

// 3. 排序
qsort(valid, cnt, sizeof(Node*), cmp_order);

// 4. 分組反轉
for (int i = 0; i + K <= cnt; i += K)
    reverse(valid + i, valid + i + K);

// 5. 重建鏈表
for (int i = 0; i < cnt - 1; i++)
    valid[i]->next = valid[i+1]->addr;
valid[cnt-1]->next = -1;

// 輸出
for (int i = 0; i < cnt; i++)
    printf("%05d %d %05d\n", valid[i]->addr, valid[i]->data, valid[i]->next);

複雜度分析

• 時間：O(N log N) 排序主導，N=1e5 完全滿足 400ms。
• 空間：O(N) 存儲節點與指針數組。

避坑指南

• 地址為 5 位數字，輸出必須 %05d 補零；-1 直接打印 -1。
• 輸入節點順序隨機，務必通過 next 串聯確定邏輯順序。
• K=1 時不反轉；K>N 時整體反轉（題目保證 K≤N）。

這道題考察「地址映射 + 邏輯排序 + 區間反轉 + 指針重建」完整鏈表操作鏈路，是鏈表題的優秀綜合訓練。