Andy Niu �����ĵ�

struct ListNode
{
    int         _Value;
    ListNode*   _PNext;

    ListNode():_Value(0),_PNext(NULL)
    {
    }

    ListNode(int value,ListNode* pNext):_Value(value),_PNext(pNext)
    {
    }
};

/*
    1、头结点需要使用指针的指针，因为：如果直接使用指针，并且删除的是头结点，
        被调用方法内，头结点变化了，而调用者的头结点没有变化
    2、注意有效性检查
    3、注意删除头结点
*/
void DeleteNode(ListNode** pPHead,ListNode* delNode)
{
    // 有效性检查
    if(pPHead == NULL || delNode==NULL)
    {
        printf("param error");
        return;
    }

    ListNode* curNode = *pPHead;
    if(curNode == delNode) //删除头结点，特殊处理一下
    {
        *pPHead = delNode->_PNext;
        delete delNode;
        delNode = NULL;         
        return;
    }

    while(curNode!=NULL)
    {
        if(curNode->_PNext == delNode)
        {
            ListNode* nextNode = delNode->_PNext;
            curNode->_PNext = nextNode;
            delete delNode;
            delNode = NULL;
            break; // 找到之后，break
        }
        curNode = curNode->_PNext;
    }
}

/*
    1、DeleteNode遍历节点，找到目标，然后删除，时间为O(n)
    2、有没有更好的办法呢？
        思路是：找到待删除节点的下一个节点，捏到一起，
        下一个节点覆盖待删除节点，然后删除下一个节点
    3、上面的思路，有一种情况需要特殊对待。
        删除的是尾节点，没有下一个节点，不能拿下一个节点覆盖
    4、注意：这种思路有一个假设条件，需要调用者保证：那就是链表包含待删除节点。
*/
void DeleteNode_2(ListNode** pPHead,ListNode* delNode)
{
    // 有效性检查
    if(*pPHead == NULL || delNode==NULL)
    {
        printf("param error");
        return;
    }

    ListNode* curNode = *pPHead;
    if(curNode == delNode) //删除头结点，特殊处理一下
    {   
        *pPHead = delNode->_PNext;
        delete delNode;
        delNode = NULL;         
        return;
    }

    // 链表至少包含两个节点
    if(delNode->_PNext == NULL) // 删除尾节点
    {
        while(curNode->_PNext !=NULL)
        {
            if(curNode->_PNext->_PNext == NULL)
            {
                delete delNode;
                curNode->_PNext = NULL;
                break; // 找到之后，break
            }
            curNode = curNode->_PNext;
        }
        return;
    }

    ListNode* nextNode = delNode->_PNext;
    *delNode = *nextNode;
    delete nextNode;        
}

void PrintListNode(ListNode* pFirst)
{
    while(pFirst!=NULL)
    {
        printf("%d ",pFirst->_Value);
        pFirst=pFirst->_PNext;
    }
    printf("\n");
}

void Test()
{
    ListNode* n6 = new ListNode(6,NULL);
    ListNode* n5 = new ListNode(5,n6);
    ListNode* n4 = new ListNode(4,n5);
    ListNode* n3 = new ListNode(3,n4);
    ListNode* n2 = new ListNode(2,n3);
    ListNode* n1 = new ListNode(1,n2);

    PrintListNode(n1);
    DeleteNode_2(&n1,n6);
    PrintListNode(n1);

    ListNode* curNode = n1;
    ListNode* next=NULL;
    while(curNode!=NULL)
    {
        next=curNode->_PNext;
        delete curNode;
        curNode=next;
    }
    curNode=NULL;
}