单链表的创建与删除

对于各种数据结构，比如set,map,二叉树等等，现在还处于很混乱的状态。。。

想通过《剑指offer》以及自己的亲手编写各种数据结构的实现与操作来熟练掌握，还是跟着此书的节奏走。

目标：在半个月内熟练！

首先，单链表的添加元素和删除元素，如下：

//单链表的添加与删除元素操作

//1、单链表中将元素添加至链表尾部（也可用于创建链表）
//思路：1、定义节点；2、由前到后遍历后插入到尾部，改变尾指针；
//      3、特殊情况：单链表为空，此时添加元素后会改动头指针，而非尾指针
struct ListNode
{
    int m_Value;
    ListNode* m_pNext;
}

void AddToListTail(ListNode** pHead, int value)
{
    //涉及指针时，先判断非空
    if(pHead == NULL)
        return;
    //创建新节点
    ListNode* pNew = new ListNode;
    pNew->m_Value = value;
    pNew->m_pNext = NULL;
    //分空、非空链表
    if(*pHead == NULL)
        *pHead = pNew;
    else
    {
        //头结点指针不能动！！！
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != NULL)
            pNode = pNode->m_pNext;
        pNode->m_pNext = pNew;
    }
}


//2、单链表中将=value的第一个元素删除
//思路：1、遍历链表，找到后删除；2、特殊情况：若头指针既是，则因为无前驱，所以修改头指针；
//      3、删除时需要前驱指针
void RemoveNode(ListNode** pHead, int value)
{
    //涉及指针，判空
    if(pHead == NULL || *pHead == NULL)
        return;
    //头结点既是
    ListNode* pToBeDeleted = NULL;
    if((*pHead)->m_Value == value)
    {        
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else   //遍历链表，找到后删除,设置了前驱
    {
        ListNode* PrepNode = *pHead;
        ListNode* pNode = (*pHead)->m_pNext;
        while(pNode != NULL && pNode->m_Value != value)
        {
            PrepNode = pNode;
            pNode = pNode->m_pNext;
        }
        if(pNode != NULL && pNode->m_Value == value)
        {
            pToBeDeleted = pNode;
            PrepNode->m_pNext = pNode->m_pNext;
        }
    }
    //删除
    if(pToBeDeleted != NULL)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;  //pToBeDeleted = NULL;重要！！！
    }
}

关于删除操作，为避免开辟前驱指针变量以及对应的赋值操作，可按作者的提示写成如下：

//3、删除元素的另一种写法，效率更高
void RemoveNode(ListNode** pHead, int value)
{
    //涉及指针，判空
    if(pHead == NULL || *pHead == NULL)
        return;
    //头结点既是
    ListNode* pToBeDeleted = NULL;
    if((*pHead)->m_Value == value)
    {        
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else   //遍历链表，找到后删除,未设置前驱
    {
        ListNode* pNode = *pHead;
　　　　 //相对应于二级指针，使用->  ->
        while(pNode->m_pNext != NULL && pNode->m_pNext->m_Value != value)
            pNode = pNode->m_pNext;

        if(pNode->m_pNext != NULL && pNode->m_pNext->m_Value == value)
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }
    //删除
    if(pToBeDeleted != NULL)
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;  //pToBeDeleted = NULL;重要！！！
    }
}