《啊哈！算法》第 2 章第 5 節(jié)撵幽，模擬鏈表的 Swift 實現(xiàn)尝蠕。
問題
為數(shù)組添加一個數(shù)血柳，仍然得到按數(shù)值大小的排序恰画，但不移動原數(shù)組的位置。
解決
用 data 存數(shù)組瓷马，用 right 記錄對應(yīng) data 中的數(shù)值的下一個數(shù)所在的編號(0 編號表示結(jié)束)拴还。為 data 尾部添加一個數(shù)后，修改 3 處 right 編號（1 新添加的數(shù) 2 此前的數(shù) 3 結(jié)束的數(shù)）欧聘，完成插入片林。
var data = [0] //初始化鏈表，前置一個空項怀骤，不打印此項
var right: [Int] = []
//待操作的數(shù)組
data += [2, 3, 5, 8, 9, 10, 18, 26, 32]
//初始化數(shù)組的 right
var count = data.count
for i in 0...count {
if i != count {
right.append(i+1)
}else{
right.append(0)
}
}
//直接在數(shù)組 data 末尾添加一個數(shù)
data.append(6)
count += 1
//從鏈表頭部開始遍歷
var t = 1
while t != 0 {
//如果當(dāng)前節(jié)點的下一個節(jié)點大于插入數(shù)费封，將數(shù)插到中間
if data[right[t]] > data[count-1] {
//新插入數(shù)的下一個節(jié)點編號等于當(dāng)前節(jié)點的下一個節(jié)點編號
right[count-1] = right[t]
//當(dāng)前節(jié)點的下一個節(jié)點編號等于新插入數(shù)的編號（最后一個）
right[t] = count - 1
//原數(shù)組最后一個節(jié)點的下一個節(jié)點編號為0（標記著數(shù)組結(jié)束）書中的 bug，缺了結(jié)束編號
right[count-1-1] = 0
break //完成插入晒喷，退出循環(huán)
}
t = right[t]
}
//遍歷輸出鏈表中的所有數(shù)
t = 1
while t != 0 {
print("\(data[t])")
t = right[t]
}
代碼在 GitHub
