功能:创建链表节点,删除节点,顺序打印,不改变原结构的情况下分别用STL中的stack实现逆序打印和利用函数递归打印

代码如下:

//链表问题
struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
};
void AddToTail(ListNode** pHead,int value);
void RemoveNode(ListNode**pHead,int value);
void PrintList(ListNode *pHead);

#include <stack>
void PrintListReverse(ListNode *pHead);//利用模版stack实现
void PrintListReverse2(ListNode *pHead);//利用递归实现

void AddToTail(ListNode** pHead,int value)
{
    if (pHead == NULL)
    {
        return;
    }

ListNode* pNode = new ListNode;
    pNode->m_nValue = value;
    pNode->m_pNext = NULL;
 
    if (*pHead == NULL)
    {
        *pHead = pNode;
    }
    else
    {//尾插法
        ListNode *pTmp = *pHead;
        while (pTmp->m_pNext != NULL)
        {
            pTmp = pTmp->m_pNext;
        }
        pTmp->m_pNext = pNode;
    }
}

void RemoveNode(ListNode**pHead,int value)
{
    if (pHead == NULL || *pHead == NULL)
    {
        return;
    }

ListNode *pNode = *pHead;
    ListNode *pTmp = NULL;

if (pNode->m_nValue == value)
    {
        *pHead = (*pHead)->m_pNext;
        delete pNode;
        pNode = NULL;
    }
    else
    {
        while(pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)//注意这里判断顺序
        {
            pNode = pNode->m_pNext;
        }
        if (pNode != NULL && pNode->m_pNext->m_nValue == value)
        {
            pTmp = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
            delete pTmp;
            pTmp = NULL;
        }
    }
}

void PrintList(ListNode *pHead)
{
    if (pHead == NULL)
    {
        return;
    }
   
    ListNode *pNode = pHead;
    while(pNode != NULL)
    {
        cout<<pNode->m_nValue<<endl;
        pNode = pNode->m_pNext;
    }
}

void PrintListReverse(ListNode *pHead)//利用STL实现
{
    if (pHead == NULL)
    {
        return;
    }
    stack<ListNode*>node;
    ListNode *pNode = pHead;
    while(pNode != NULL)
    {
        node.push(pNode);
        pNode = pNode->m_pNext;
    }
    while (!node.empty())
    {
        pNode = node.top();
        cout<<pNode->m_nValue<<endl;
        node.pop();
    }
}

void PrintListReverse2(ListNode *pHead)
{
    if (pHead != NULL)
    {
        if (pHead->m_pNext != NULL)
        {
            PrintListReverse2(pHead->m_pNext);
        }
        cout<<pHead->m_nValue<<endl;
    }
}

05-04 01:21