[算法討論]本算法先找結果鏈表的第一個元素這是因為題目要求結果表要遞增有序(即刪除重復元素)這就要求當前待合並到結果表的元素要與其前驅比較由於初始pre=A(頭結點的頭指針)這時的data域無意義不能與後繼比較元素大小因此就需要確定第一個元素當然不要這樣作而直接進入下面循環也可以但在鏈入結點時必須先判斷pre是否等於A這占用了過多的時間因此先將第一結點鏈入是可取的
算法中的第二個問題是要求時間復雜度為O(|A|+|B|+|C|)這就要求各個表的工作指針只能後移(即不能每次都從頭指針開始查找)本算法滿足這一要求
最後一個問題是當BC有一表為空(即B和C已無公共元素時)要將A的剩余部分鏈入結果表
．[題目分析]循環單鏈表L和L數據結點個數分別為m和n 將二者合成一個循環單鏈表時需要將一個循環鏈表的結點(從第一元素結點到最後一個結點)插入到另一循環鏈表的第一元素結點前即可題目要求用最快速度將兩表合並因此應找結點個數少的鏈表查其尾結點
LinkedList Union(LinkedList LL;int mn)∥L和L分別是兩循環單鏈表的頭結點的指針m和n分別是L和L的長度本算法用最快速度將L和L合並成一個循環單鏈表
{if(m<||n<) {printf(表長輸入錯誤\n);exit();}
if(m<n)∥若m<n則查L循環單鏈表的最後一個結點
{if(m==)return(L);∥L為空表
else{p=L;
while(p>next!=L) p=p>next;∥查最後一個元素結點
p>next=L>next;∥將L循環單鏈表的元素結點插入到L的第一元素結點前
L>next=L>next;
free(L);∥釋放無用頭結點
}
}∥處理完m<n情況
else∥ 下面處理L長度小於等於L的情況
{if(n==)return(L);∥L為空表
else{p=L;
while(p>next!=L) p=p>next;∥查最後元素結點
p>next=L>next;∥將L的元素結點插入到L循環單鏈表的第一元素結點前
L>next=L>next;
free(L);∥釋放無用頭結點
}
}∥算法結束
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23353.html
