演算法中階・鏈結串列的指標操作
用 dict 當 next 指標:局部反轉、快慢指標找環的入口、找中點反轉後交錯合併。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
設定版本鏈局部反轉
中等鏈結串列設定檔的版本串成一條鏈:每個版本記著「下一個版本」是誰,最後一個版本的下一個寫成
-。這條鏈存成 dictnxt(版本 → 下一個版本)。維運人員要把鏈上第 l 到第 r 個版本(從 1 起算,含兩端)的順序反過來,其他版本不動。輸入:
第 1 行:組數 t
每組:第 1 行是
n head l r(節點數、第一個版本、反轉範圍,1 ≤ l ≤ r ≤ n),接下來 n 行是版本 下一個版本(順序是打亂的)輸出:每組
- 第 1 行:反轉後從頭走到尾的版本,以
->連接 - 第 2 行:
changed k,k 是 next 指向改變的版本數 - 接下來 k 行:
版本 原本的下一個 新的下一個,依版本名稱的字串順序排列
要求:直接改
nxt的指向完成反轉(可以加一個虛擬的頭節點),不要把整條鏈轉成 list 切片反轉再重建。範例輸入:
1
4 v1 2 3
v1 v2
v2 v3
v3 v4
v4 -
範例輸出:
v1 -> v3 -> v2 -> v4
changed 3
v1 v2 v3
v2 v3 v4
v3 v4 v2
類型對應:LeetCode「Reverse Linked List II」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 第 1 行:反轉後從頭走到尾的版本,以
- 02
血緣鏈找環的入口
中等鏈結串列排程系統裡,每張資料表最多觸發一張下游表(例如
src_b更新後觸發stg_b)。設定寫錯時會形成循環觸發。給一個起點,沿著「下游」一直走:走到沒有下游的表就停;如果會無限繞圈,要找出環的入口(從起點出發,第一張走到的、位在環上的表)、環上有幾張表,以及起點走幾步才進到入口。輸入:
第 1 行:表數 n
接下來 n 行:
表 下游表(沒有下游寫-;每張表剛好出現在一行的開頭,下游表一定是有列出的表或-)下一行:查詢數 q
接下來 q 行:每行一個起點
輸出:每個查詢一行
- 不會繞圈:
END 最後一張表 k,k 是從起點到最後一張表經過的表數(含頭尾) - 會繞圈:
CYCLE 入口 環長 前段步數;起點本身就在環上時,入口是起點、前段步數是 0
要求:用快慢指標(Floyd)判斷有沒有環、找入口,額外空間 O(1);不要用 set 記走過的表。
範例輸入:
5
a b
b c
c d
d b
e -
3
a
e
c
範例輸出:
CYCLE b 3 1
END e 1
CYCLE c 3 0
類型對應:LeetCode「Linked List Cycle II」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 不會繞圈:
- 03
巡檢順序頭尾交錯
中等鏈結串列叢集節點串成一條巡檢鏈 L0 → L1 → … → L(n−1)(dict
nxt記每個節點的下一個,最後一個的下一個是-)。為了讓新舊節點交錯檢查,要把順序改成 L0 → L(n−1) → L1 → L(n−2) → L2 → …,直到每個節點都排進去。做法分三步:用快慢指標找出前半段的最後一個節點(前半段有 ⌈n/2⌉ 個節點)、把後半段反轉、再把兩段交錯合併。
輸入:
第 1 行:組數 t
每組:第 1 行是
n head,接下來 n 行是節點 下一個節點(順序是打亂的)輸出:每組兩行
mid 前半段最後一個節點- 重排後的順序,以
->連接
要求:照上面三步改指向完成,不要把節點放進 list 用索引交錯取。
範例輸入:
1
3 a
a b
b c
c -
範例輸出:
mid b
a -> c -> b
類型對應:LeetCode「Reorder List」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了