阿摩線上測驗
29 將 2 個分別由 m 個和 n 個節點所構成的雙向串列（doubly linked list）合併成 1 個雙向串列所花費的時間為：
(A)Q(1)
(B)Q(m+n)
(C)Q(m-n)
(D)Q(min(m, n))
答案：登入後查看
統計： A(59), B(40), C(22), D(35), E(0) #1208972
統計： A(59), B(40), C(22), D(35), E(0) #1208972
詳解 (共 6 筆)
梅川依芙
#4799813
雙向鏈結串列可以從頭遍歷到尾, 也可以從尾遍歷到頭
1
0
Kari
#4195091
Winx：
你都說挑頭或尾了，代表有一條是要挑尾巴，所以要先遍歷所有節點不是嗎?
或者兩個頭連接在一起，最後要返回新的head指標，一樣要遍歷短的那條串列找到尾巴
雙向鏈結串列有固定的head指標指向第一個節點，跟你舉例的繩子應該不一樣吧?
繩子像是佇列，你可以隨時取得front及rear節點，雙向鏈結串列要找到尾巴就要先遍歷所有節點一次(題目並沒有說是環狀雙向鏈結串列)
能不能用畫圖來說說你的方法可不可行?
如果是要真的寫成程式碼或演算法並進行雙向鏈結串列的合併
我認為都要遍歷短的那條串列才有可能正常執行
這是我想像中的雙向鏈結串列
0
0
Kari
#4099018
最佳解寫 "doubly linked list 做insert即可"
但我還是不懂，是否有人能說明?
我的思維邏輯是：此雙鏈非循環，因此必須找到短的一端的尾巴才能跟另一條雙鏈的頭串接上，故選(D)
但答案卻是(A)，願聞其詳
0
0