#include<stack>

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)

    {

        printf("Error to connect two nodes.\n");

        exit();

    }

    pCurrent->m_pNext = pNext;

}

void PrintListNodeValue(ListNode* pNode)

{

    if (pNode == nullptr)

        printf("The node is nullptr.\n");

    else

        printf("The value of the node is %d .\n", pNode->m_nValue);

}

void PrintListNode(ListNode* pHead)

{

    printf("PrintList starts.\n");

    ListNode* pNode = pHead;

    while (pNode != nullptr)

    {

        printf("%d\t", pNode->m_nValue);

        pNode = pNode->m_pNext;

    }

    printf("\nPrintList ends.\n");

}

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;

    }

}

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)

        {

            pToBeDeleted = pNode->m_pNext;

            pNode->m_pNext = pNode->m_pNext->m_pNext;

        }

    }

    if (pToBeDeleted != nullptr)

    {

        delete pToBeDeleted;

        pToBeDeleted = nullptr;

    }

}

void PrintListReversingly_Iteratively(ListNode* pHead)

{

    std::stack<ListNode*>nodes;

    ListNode* pNode = pHead;

    while (pNode != nullptr)

    {

        nodes.push(pNode);

        pNode = pNode->m_pNext;

    }

    while (!nodes.empty())

    {

        pNode = nodes.top();

        printf("%d\t", pNode->m_nValue);

        nodes.pop();

    }

}

void PrintListReversingly_Recursively(ListNode* pHead)

{

    if (pHead != nullptr)

    {

        if (pHead->m_pNext != nullptr)

        {

            PrintListReversingly_Recursively(pHead->m_pNext);

        }

        printf("%d\t", pHead->m_nValue);

    }

}

void Test(ListNode* pHead)

{

    PrintListNode(pHead);

    PrintListReversingly_Iteratively(pHead);

    printf("\n");

    PrintListReversingly_Recursively(pHead);

}

void Test1()

{

    printf("\nTest1 begins.\n");

    ListNode* pNode1 = CreateListNode();

    ListNode* pNode2 = CreateListNode();

    ListNode* pNode3 = CreateListNode();

    ListNode* pNode4 = CreateListNode();

    ListNode* pNode5 = CreateListNode();

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    Test(pNode1);

    DestroyList(pNode1);

}

int main(int argc, char* argv[])

{

    Test1();

    getchar();

}