面试题18: O(1)删除链表节点 应该加强边界检查

[bodu93]

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
{
    if(!pListHead || !pToBeDeleted)
        return;

    // 要删除的结点不是尾结点
    if(pToBeDeleted->m_pNext != nullptr)
    {
        ListNode* pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;

        delete pNext;
        pNext = nullptr;
    }
    // 链表只有一个结点，删除头结点（也是尾结点）
    else if(*pListHead == pToBeDeleted)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
        *pListHead = nullptr;
    }
    // 链表中有多个结点，删除尾结点
    else
    {
        ListNode* pNode = *pListHead;
        // 加强边界检查，防止意外输入造成core dump
        while(pNode->m_pNext != nullptr && pNode->m_pNext != pToBeDeleted)
        {
            pNode = pNode->m_pNext;            
        }

        if (pNode->m_pNext == pToBeDeleted)
        {
            pNode->m_pNext = nullptr;
            delete pToBeDeleted;
            pToBeDeleted = nullptr;
        }
    }
}

[zzw1123]

想问下，函数形参里边ListNode** pListHead这里，为什么要用两个星号呢？ 一个星号表示头指针不就可以了吗？ 对链表还是理解的不太到位，请指正~

[bodu93]

@zzw1123 因为这个函数可能修改头指针(将头指针赋空值)。在C语言中函数传参本质上是传值，即拷贝实参。所以要修改实参只能传递实参的地址，利用指针的间接性进行修改。而此处实参是一个指针，所以要修改指针，就要传递该指针的地址，于是就是两个星号啦:)

[zzw1123]

@bodu93 明白啦~~谢谢！

[woshigerunze]

@zzw1123 因为这个函数返回值是void所以必须改掉头结点本身的结构，所以不是一个的值传递。如果有返回值的话可以用一个。 另外ListNode* head可以写成ListNode& head。

[forwardwfg]

@bodu93 请问为什么 delete了 pToBeDeleted还要让pToBeDeleted 指向 nullptr，del了还不可以？

[woshigerunze]

@WeifaGan你可以定义一个new一个字符串，delete他的指针，但是可以还是可以（有时）cout这个字符串的。delete只是表示这个内存可以被其他人用，但是内容要等下次写入时覆盖，不会立即删除。设置为nullptr可以防止误用（cout delete的指针是未定义行为）

[forwardwfg]

@woshigerunze 原来如此！谢谢解答！