是否可以刪除鏈表中的最後一個節點？

寫一個函數刪除鏈表中的節點，這是解決方案：

void deleteNode(Node* toDelete) { 

    // this function essensially first copies the data from the next pointer 
    // and then, deletes the next pointer 
    // However, it doesn't work if trying to delete the last element in the list 

    Node *temp = toDelete->next; // create a temp, assign to the one after toDelete 
    toDelete->data = temp->data; // change toDelete's data to the one's after it 
    toDelete->next = temp->next; // change toDelete's next to the one's after it 

    delete temp; 
    temp = nullptr; 
}

如何更改我的解決方案，以便能夠刪除鏈接列表中的最後元素，給定只有指針最後一個節點？

來源

2013-08-07 Oleksiy

最後一個節點與其他節點有什麼不同？您如何測試？ – juanchopanza

它沒有指向什麼？接下來是nullptr – Oleksiy

所以，也許你可以使用這些信息爲該節點做一些不同的事情。 – juanchopanza

顯然你不能;前一個節點指向一個有效的節點，並且沒有辦法改變它。

你可以做的是將一個標記節點添加到列表的末尾。您永遠不會刪除該節點，也不會使用它來存儲數據。那麼你的解決方案將適用於所有數據節點。這不需要對節點結構進行任何更改，但需要更改對列表進行迭代的方式。

來源

2013-08-07 07:20:46

我想知道在「我不允許改變結構」下面是否會被禁止。我認爲它會，但我給你+1假設它不會:-) –

不，這不可能用單鏈表。

原因是您需要修改倒數第二個節點（以使其next指針爲空）。但是沒有辦法從最後一個節點找到該節點。

一般來說，只能給出指向節點的指針，不能從單向鏈表中刪除一個節點。

你目前正在做的事實質上是一個「作弊」，因爲你並沒有真的刪除指向的節點。您正在變更列表，然後刪除指向的節點的後繼者。當你調用這個函數時，如果某處的其他代碼持有一個指向該後繼者的指針 - 它們的指針會失效。所以你刪除了指向的數據元素，但是你並沒有刪除指向的節點。

來源

2013-08-07 07:18:10

要明確：這將適用於所有節點，而不僅僅是最後一個，對嗎？ – juanchopanza

@juanchopanza：同意。我正在編輯這樣說，但後來我解釋了爲什麼提問者的當前代碼看起來像是刪除了指向的節點，但實際上並沒有。 –

爲了處理單個鏈接列表中的節點刪除，您需要修改節點前後的節點。

  +-----+ +----------+ +------+ 
header----->|  |->| toDelete |->|  | 
      +-----+ +----------+ +------+

您需要一個指向列表第一個元素的指針，否則根據數據結構的性質不可能做你想要的。

首先找到需要刪除的節點之前的節點，例如：

Node* before = header; 
for (;before->next != toDelete; before = before->next) {;}

現在要做before->next = toDelete->next如果toDelete是這將是最後一個節點一個nullptr否則一個指向下一個節點

（當然，你需要在這兩種情況下，刪除toDelete點什麼）

來源

2013-08-07 07:38:11

對於ASCII藝術+1 – Hulk

是否可以刪除鏈表中的最後一個節點？

回答

相關問題