地特三等申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言（C-like pseudo code）完成下列動作。 (一)請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分） (二)請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分） (三)請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言（C-like pseudo code）完成下列動作。 (一)請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分） (二)請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分） (三)請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
📝 此題為申論題，共 3 小題
小題 (一)
請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分）
思路引導 VIP
刪除單向鏈結串列中特定節點的核心，在於必須找到該節點的「前驅節點」以修改指標方向。觀察附圖可知，指標 A 所指的節點恰為指標 C 所指節點的前驅（即 A 的 link 指向 C），因此直接修改 A 的指標繞過 C，並將 C 的記憶體釋放即可。
小題 (二)
請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分）
思路引導 VIP
觀察題目圖示，解題關鍵在於發現指標 C 已經固定指向 A 的下一個節點（即 C 等同於 A->link）。因此，要將 B 串列插入 A 串列，只需將 A 節點的指標指向 B 串列的首節點（B->link），再將 B 節點（串列尾）的指標指向 C 即可，正好能用兩行虛擬碼完成合併。
小題 (三)
請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
思路引導 VIP
要在單向鏈結串列中將節點插入至某節點之「前」，核心挑戰在於單向結構無法直接取得前驅節點。解題關鍵是利用輔助指標 C 走訪環狀串列一圈，定位出 A 的前驅節點後，再進行 B 節點的指標串接。