### 說明:無環鏈表。這道題可以用O(1)的時間刪除鏈表的鏈頭和中間節點,但是刪除鏈尾還是要O(n)。所以平均時間為O(1)。
### 思路:其實并不是真正刪除該節點,因為要刪除這個節點必須要找到它的前一個節點,而我們沒有 m_prev 指針,所以我們刪除它的后一個節點,因為這個節點的前一個指針我們已經知道了,就是原本要刪除的節點,但在刪除后一個節點前,我們要把它的值替換掉原本要刪除的節點的值。但是最后那個節點不能這么做,因為它是最后的節點~**注意**:上面的思路我已經假設要刪除的節點在鏈表中了。還有一點是,如果刪除的是鏈表中**惟一的一個節點**,那么鏈頭會被修改,所以我們要傳入鏈頭(指針)的指針。
下面是代碼實現(出自《劍指 offer》):
```
void deleteNode(SList **pHead, SList *pToBeDeleted)
{
if (pHead == nullptr || pToBeDeleted == nullptr) {
return;
}
// 要刪除的節點不是尾節點
if (pToBeDeleted->m_next != nullptr) {
SList *pNext = pToBeDeleted->m_next;
pToBeDeleted->m_data = pNext->m_data;
pToBeDeleted->m_next = pNext->m_next;
delete pNext;
pNext = nullptr;
} else if (*pHead == pToBeDeleted) { // 刪除唯一的一個節點
delete pToBeDeleted;
pToBeDeleted = nullptr;
*pHead = nullptr;
} else { // 鏈表中有多個節點,刪除鏈尾節點
// 只能先找到前一個節點
SList *pPrev = *pHead;
while (pPrev->m_next != pToBeDeleted) {
pPrev = pPrev->m_next;
}
pPrev->m_next = nullptr;
delete pToBeDeleted;
pToBeDeleted = nullptr;
}
}
```