关于链表的预备知识

定义结点

struct ListNode
{
     int m_nValue;
     ListNode* m_pnext;
};

创建链表结点

ListNode* CreateListNode(int value)
{
    ListNode* pNode = new ListNode();
    pNode->m_nValue = value;
    pNode->m_pNext = nullptr;
    return pNode;
}

连接链表各结点

void ConnectListNodes(ListNode* pCurrent,ListNode* pNext)
{
    if(pCurrent == nullptr)
    {
        cout<<"Error to connect two nodes!"<<endl;
        exit(1);
    }
    pCurrent->m_pNext = pNext;
}

打印链表结点的值

void PrintListNode(ListNode* pNode)
{
    if(pNode == nullptr)
    {
        cout<<"Error to print node, the node is nullptr !"<<endl;
    }
    else
    {
        cout<<"The value in node is "<<pNode->m_nValue<<endl;
    }
}

打印整个链表中的值

void PrintList(ListNode* pHead)
{
    cout<<"Print list starts:"<<endl;
    ListNode* pNode = pHead;
    while(pNode!=nullptr)
    {
        cout<<pNode->m_nValue<<endl;
        pNode = pNode->m_pNext;
    }
    cout<<"Print list ends."<<endl;
}

删除整个链表

void DestroyList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode!=nullptr)
    {
        pHead = pHead->m_pNext;
        delete pNode;
        pNode = pHead;
    }
}

在链表尾部加入结点

void AddToTail(ListNode ** pHead,int value)
{
    ListNode* pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_pNext = nullptr;
    if(*pHead == nullptr)    //判断如果此时链表为空，则插入的节点为头节点
    {
        *pHead = pNew;
    }
    else
    {
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != nullptr)
            pNode = pNode->m_pNext;
        pNode->m_pNext = pNew;
    }
}

特别注意，pHead是一个指向指针的指针，当我们往一个空链表中插入结点时，新插入的节点就是链表的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了这个函数pHead仍旧是一个空指针。
在链表中找到第一个含有某值的节点并删除此节点

void RemoveNode(ListNode **pHead,int value)
{
    if(pHead == nullptr || *pHead == nullptr)
        return;
    ListNode* pToBeDeleted = nullptr;
    if((*pHead)->m_nValue == value)
    {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext; 
    }
    else
    {
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value)
              pNode = pNode->m_pNext;
         if(pNode->m_pNext !=nullptr && pNode->m_pNext->m_nValue == value)   //找到value值的上一个节点
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext; 
        }
    }
    if(pToBeDeleted != nullptr)
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}

总结：考虑情况要全面。