Andy Niu �����ĵ�

Andy Niu

Andy Niu Help  1.0.0.0

变量

 删除节点
 

详细描述

变量说明

删除节点
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;
}
Copyright (c) 2015~2016, Andy Niu @All rights reserved. By Andy Niu Edit.