AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・中階・3 題

演算法中階・鏈結串列的指標操作

用 dict 當 next 指標:局部反轉、快慢指標找環的入口、找中點反轉後交錯合併。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 01

    設定版本鏈局部反轉

    中等鏈結串列

    設定檔的版本串成一條鏈:每個版本記著「下一個版本」是誰,最後一個版本的下一個寫成 -。這條鏈存成 dict nxt(版本 → 下一個版本)。維運人員要把鏈上第 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 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 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答