我所能想到的是以下三種情況：
1）可以在鏈表中設定一個int size，用來計數當前鏈表中結點的個數，如果要洗掉倒數第k個結點，就可以順序便利到（size-k+1）的位置，洗掉該結點就是要求的倒數第k個結點；
2）第二種類似1），如果給定的鏈表定義的時候沒有設定size，那么我們就要自行的將整個鏈表遍歷一遍計算結點個數，然后同1），遍歷到（size-k+1），洗掉結點；
以上兩種辦法比較容易想到，可是比較笨拙，時間復雜度是o(n2)，不夠優越；
3）使用兩個指標p1,p2，起始時p1指向頭結點，p2則指向第k個結點，也就是p1到p2包含的結點的個數是k個，之后就很清晰了，p1,p2同時向后移動，當p2->link==NULL時，p2遍歷到鏈表結尾，此時的p1所指向的結點不就是倒數第k個結點嗎。
第三種辦法的時間復雜度降到了o(n)，這是我所掌握的最優越的演算法了。
PS：每種情況都要考慮到鏈表中不存在倒數第k個結點的情況（即k＞鏈表結點總數）
~歡迎修正補充~
uj5u.com熱心網友回復：
前兩種時間復雜度為啥是O(n^2)？不是O(n)嗎？uj5u.com熱心網友回復：
第三種。你起始時，p2是怎么指向第k個結點的？uj5u.com熱心網友回復：
我是新手剛剛學資料結構，第一個時間復雜度是o(n)沒錯，可是第二個，因為遍歷第一次計算size，遍歷第二次的時候才去找結點洗掉，每個都是o(n)，我不太清楚這兩次遍歷是算在一起，算為o(n2)，還是各自算是o(n)
，還有第三個找第k個結點，我就是從頭遍歷到第k個結點找到他的，這個辦法是不是也不夠優越啊
uj5u.com熱心網友回復：
多謝指教！（發這些持學習態度）
uj5u.com熱心網友回復：
三種的時間愛你復雜度都是O(n)。
// 時間復雜度為：O(n^2)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
}
}
// 時間復雜度為：O(n)
for (int i = 0; i < n; ++i) {
}
for (int i = 0; i < n; ++i) {
}
uj5u.com熱心網友回復：
這回就搞清楚這個問題了感謝
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/153130.html
標籤：數據結構與算法
上一篇：【Tensorflow slim API】影像分類訓練時在tensorboard中可視化每層卷積的輸出結果（便于觀察每層輸出！步驟清晰有用！）
下一篇：求問大學資料結構課程問題！！