SanfenR的博客

链表删除(day3)

发表于 |

假设链表……—A–B–C–D….，要删除B。一般的做法是遍历链表并记录前驱节点，修改指针，时间为O(n)。删除节点的实质为更改后驱指针指向。 这里，复制C的内容至B(此时B，C同时指向D)，删除节点C，即达到间接删除节点B的目的。 倘若B是链尾节点。则需要线性遍历寻找前驱节点。以上思路，时间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct ListNode {
    int m_nKey;
    ListNode *m_pNext;
};
void deleteNode(ListNode* pListHead, ListNode* pToBeDeleted) {
    if (!pListHead || !pToBeDeleted) {
        return;
    }
    if (pListHead == pToBeDeleted){
        delete pListHead;
        pListHead = NULL;
        pToBeDeleted = NULL;
    } else if (pToBeDeleted->m_pNext != NULL) {
        ListNode *pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nKey = pNext->m_nKey;
        pToBeDeleted->m_pNext = pNext->m_pNext;
        delete pNext;
        pNext = NULL;
    } else {
        ListNode* pNode = pListHead;
        while(pNode->m_pNext != pToBeDeleted) {
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = NULL;
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

源码github