類似本題敘述的其它題解答如下
()[題目分析]本題將線性表la和lb連接要求時間復雜度為O()且占用輔助空間盡量小應該使用只設尾指針的單循環鏈表
LinkedList Union(LinkedList lalb)∥la和lb是兩個無頭結點的循環單鏈表的尾指針本算法將lb接在la後成為一個單循環鏈表
{ q=la>next;∥q指向la的第一個元素結點
la>next=lb>next;∥將lb的最後元素結點接到lb的第一元素
lb>next=q;∥將lb指向la的第一元素結點實現了lb接在la後
return(lb);∥返回結果單循環鏈表的尾指針lb
}∥算法結束
[算法討論]若循環單鏈表帶有頭結點則相應算法片段如下
q=lb>next;∥q指向lb的頭結點;
lb>next=la>next;∥lb的後繼結點為la的頭結點
la>next=q>next;∥la的後繼結點為lb的第一元素結點
free(q);∥釋放lb的頭結點
return(lb);∥返回結果單循環鏈表的尾指針lb
()[題目分析]本題要求將單向鏈表ha和單向循環鏈表hb合並成一個單向鏈表要求算法所需時間與鏈表長度無關只有使用帶尾指針的循環單鏈表這樣最容易找到鏈表的首尾結點將該結點序列插入到單向鏈表第一元素之前即可
其核心算法片段如下(設兩鏈表均有頭結點)
q=hb>next;∥單向循環鏈表的表頭指針
hb>next=ha>next;∥將循環單鏈表最後元素結點接在ha第一元素前
ha>next=q>next;∥將指向原單鏈表第一元素的指針指向循環單鏈表第一結點
free(q);∥釋放循環鏈表頭結點
若兩鏈表均不帶頭結點則算法片段如下
q=hb>next;∥q指向hb首元結點
hb>next=ha;∥hb尾結點的後繼是ha第一元素結點
ha=q;∥頭指針指向hb的首元結點
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23354.html
