84669 人學習
152542 人學習
20005 人學習
5487 人學習
7821 人學習
359900 人學習
3350 人學習
180660 人學習
48569 人學習
18603 人學習
40936 人學習
1549 人學習
1183 人學習
32909 人學習
在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?
小伙看你根骨奇佳,潜力无限,来学PHP伐。
我同意上面brayden的說法,這個問題在資料結構與演算法上沒有任何意義,應該是樓主看錯題了。問題是O(1)時間刪除循環單鍊錶的某個節點才對,下面簡單給出O(1)時間刪除循環單鍊錶的某個節點的解: 假定要刪除的節點是ListNode *toBeDeleted 要求在O(1)時間內刪除,就肯定不能用遍歷了,由於是單項鍊表,不用遍歷是找不到該節點的前一個節點的,所以就不能用常規鍊錶刪除的方法了。 由於我們知道要刪除的節點ListNode *toBeDeleted,所以我們可以直接得到它的後一個節點ListNode *pNext。我們可以用pNext的內容覆蓋掉toBeDeleted節點,然後將節點toBeDeleted連結到pNext的下一個節點之後將pNext節點刪除即可。以下是一個簡單的示意圖(假設要刪除i):
ListNode *toBeDeleted
ListNode *pNext
pNext
toBeDeleted
原理很簡單就是:完全複製下一個節點,然後在刪除下一個節點,以達到刪除本節點的假象。
之前用過類似的資料結構,沒必要寫什麼記憶體分配函數。主要實現想法如下:
但是這樣的做的主要問題是:如果節點是包含資源的,那麼資源必然會洩漏。
我同意上面brayden的說法,這個問題在資料結構與演算法上沒有任何意義,應該是樓主看錯題了。問題是O(1)時間刪除循環單鍊錶的某個節點才對,下面簡單給出O(1)時間刪除循環單鍊錶的某個節點的解:
假定要刪除的節點是
ListNode *toBeDeleted
要求在O(1)時間內刪除,就肯定不能用遍歷了,由於是單項鍊表,不用遍歷是找不到該節點的前一個節點的,所以就不能用常規鍊錶刪除的方法了。
由於我們知道要刪除的節點
ListNode *toBeDeleted
,所以我們可以直接得到它的後一個節點ListNode *pNext
。我們可以用pNext
的內容覆蓋掉toBeDeleted
節點,然後將節點toBeDeleted
連結到pNext
的下一個節點之後將pNext
節點刪除即可。以下是一個簡單的示意圖(假設要刪除i):之前用過類似的資料結構,沒必要寫什麼記憶體分配函數。主要實現想法如下:
但是這樣的做的主要問題是:如果節點是包含資源的,那麼資源必然會洩漏。