算法設計題
．[題目分析]因為兩鏈表已按元素值遞增次序排列將其合並時均從第一個結點起進行比較將小的鏈入鏈表中同時後移鏈表工作指針該問題要求結果鏈表按元素值遞減次序排列故在合並的同時將鏈表結點逆置
LinkedList Union(LinkedList lalb)
∥lalb分別是帶頭結點的兩個單鏈表的頭指針鏈表中的元素值按遞增序排列本算法將兩鏈表合並成一個按元素值遞減次序排列的單鏈表
{ pa=la>next; pb=lb>next;∥papb分別是鏈表la和lb的工作指針
la>next=null;∥la作結果鏈表的頭指針先將結果鏈表初始化為空
while(pa!=null && pb!=null)∥當兩鏈表均不為空時作
if(pa>data<=pb>data)
{ r=pa>next;∥將pa 的後繼結點暫存於r
pa>next=la>next;∥將pa結點鏈於結果表中同時逆置
la>next=pa;
pa=r;∥恢復pa為當前待比較結點
}
else
{r=pb>next;∥ 將pb 的後繼結點暫存於r
pb>next=la>next;∥將pb結點鏈於結果表中同時逆置
la>next=pb;
pb=r;∥恢復pb為當前待比較結點
}
while(pa!=null)∥將la表的剩余部分鏈入結果表並逆置
{r=pa>next; pa>next=la>next; la>next=pa; pa=r; }
while(pb!=null)
{r=pb>next; pb>next=la>next; la>next=pb; pb=r; }
}∥算法Union結束
［算法討論］上面兩鏈表均不為空的表達式也可簡寫為while(pa&&pb)兩遞增有序表合並成遞減有序表時上述算法是邊合並邊逆置也可先合並完再作鏈表逆置後者不如前者優化算法中最後兩個while語句不可能執行兩個只能二者取一即哪個表尚未到尾就將其逆置到結果表中即將剩余結點依次前插入到結果表的頭結點後面
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23365.html
