《剑指offer》第五题(重要!从尾到头打印链表)

文件main.cpp

// 从尾到头打印链表
// 题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。

#include <iostream>
#include <stack>
#include "List.h"
using namespace std;

void PrintListReversingly_Iteratively(ListNode* pHead)//解法一:使用栈
{
    stack<ListNode*> nodes;//定义一个类型为ListNode*的栈,其名为nodes

    ListNode* pNode = pHead;
    while (pNode != NULL)//压入栈
    {
        nodes.push(pNode);//在栈顶上堆进一个元素
        pNode = pNode->m_pNext;
    }

    while (!nodes.empty())//弹出栈并打印
    {
        pNode = nodes.top();//返回栈顶的元素,并不会删除  
        cout << pNode->m_nValue<<"\t";
        nodes.pop();//删除掉栈顶上的元素
    }
}

void PrintListReversingly_Recursively(ListNode* pHead)//解法二:递归。但是容易因为链表过大而栈溢出
{
    if (pHead != NULL)
    {
        if (pHead->m_pNext != NULL)
        {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }

        cout << pHead->m_nValue << "\t";
    }
}

// ====================测试代码====================
void Test(ListNode* pHead)
{
    PrintList(pHead);
    PrintListReversingly_Iteratively(pHead);
    printf("\n");
    PrintListReversingly_Recursively(pHead);
}

// 1->2->3->4->5
void Test1()
{
    printf("\nTest1 begins.\n");

    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);
    ListNode* pNode4 = CreateListNode(4);
    ListNode* pNode5 = CreateListNode(5);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);
    ConnectListNodes(pNode3, pNode4);
    ConnectListNodes(pNode4, pNode5);
    //也可以如下建立链表
    /*AddToTail(&pNode1, 2);
    AddToTail(&pNode1, 3);
    AddToTail(&pNode1, 4);
    AddToTail(&pNode1, 5);*/
    Test(pNode1);

    DestroyList(pNode1);
}

// 只有一个结点的链表: 1
void Test2()
{
    printf("\nTest2 begins.\n");

    ListNode* pNode1 = CreateListNode(1);

    Test(pNode1);

    DestroyList(pNode1);
}

// 空链表
void Test3()
{
    printf("\nTest3 begins.\n");

    Test(NULL);
}

int main()
{
    Test1();
    Test2();
    Test3();

    system("pause");
}

文件List.h

#ifndef LIST_H
#define LIST_H


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

ListNode* CreateListNode(int value);
void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);
void PrintListNode(ListNode* pNode);
void PrintList(ListNode* pHead);
void DestroyList(ListNode* pHead);
void AddToTail(ListNode** pHead, int value);
void RemoveNode(ListNode** pHead, int value);

#endif

文件List.cpp

#include <iostream>
#include "List.h"
using namespace std;

ListNode* CreateListNode(int value)//创建一个节点,返回地址
{
    ListNode* pNode = new ListNode();//第一步:创建
    pNode->m_nValue = value;//第二步:给数据赋值
    pNode->m_pNext = NULL;//第三步:给下个节点地址附上NULL

    return pNode;
}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)//将两个节点连接起来
{
    if (pCurrent == NULL)//第一步:判断当前节点存在否
    {
        cout << "Error to connect two nodes.\n";
        exit(1);//告诉系统,正常退出,结束进程
    }

    pCurrent->m_pNext = pNext;//第二步:将下一节点地址赋给当前节点的m_pNext
}

void PrintListNode(ListNode* pNode)//打印当前节点的数值
{
    if (pNode == NULL)//第一步:判断当前节点存在否
    {
        printf("The node is NULL.\n");
    }
    else
    {
        cout << "The key in node is %d.\n" << pNode->m_nValue;//第二步:打印
    }
}

void PrintList(ListNode* pHead)//打印整个链表的数值
{
    printf("PrintList starts.\n");

    ListNode* pNode = pHead;//第一步:建立一个pNode
    while (pNode != NULL)//第二步:检查当前节点为NULL不
    {
        cout << pNode->m_nValue << "\t";//第三步:不为空就打印
        pNode = pNode->m_pNext;//第四步:当前节点打印完,就把下一节点地址给pNode
    }

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

void DestroyList(ListNode* pHead)//删除整个链表
{
    ListNode* pNode = pHead;//第一步:建立一个pNode
    while (pNode != NULL)//第二步:检查当前节点为NULL不
    {
        pHead = pHead->m_pNext;//第三步:不为空,头结点后移
        delete pNode;//第四步:删除结点pNode
        pNode = pHead;//第五步:头结点赋给pNode
    }
}

void AddToTail(ListNode** pHead, int value)//在链表最后添加节点,注意这里头结点一定是指向指针的指针
{
    ListNode* pNew = CreateListNode(value);//第一步:建立一个新节点

    if (*pHead == NULL)//第二步:若头结点为空,即空链表,就直接复制新节点就行了
    {
        *pHead = pNew;//这里是为什么 头结点一定是指向指针的指针 的关键,如果不是,出了这个函数,头结点会还是空的
    }

    else
    {
        ListNode* pNode = *pHead;//第三步:找到链表末尾
        while (pNode->m_pNext != NULL)
            pNode = pNode->m_pNext;

        pNode->m_pNext = pNew;//第四步:插入末尾
    }
}

void RemoveNode(ListNode** pHead, int value)//移除值为value的节点,这里头结点一定是指向指针的指针
{
    if (pHead == NULL || *pHead == NULL)//第一步:检查头指针和头结点存在不
        return;

    ListNode* pToBeDeleted = NULL;//第二步:创建一个节点pToBeDeleted留着被删除时候用
    if ((*pHead)->m_nValue == value)//第三步:先检查头结点,这个特殊
    {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else
    {
        ListNode* pNode = *pHead;
        while (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue != value)//第四步:头结点没事,那就建立一个pNode向下找,注意判断条件
            pNode = pNode->m_pNext;//是确认pNode的下个节点不为空,且下个节点的值不是value,pNode才往下走

        if (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)//第五步:若下个节点的值是value,将下个节点赋给待删除节点pToBeDeleted,且将pNode的下下个节点地址赋给pNode的m_pNext
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }

    if (pToBeDeleted != NULL)//第六步:删除节点pToBeDeleted
    {
        delete pToBeDeleted;
        pToBeDeleted = NULL;
    }
}

 

上一篇:在一个排序的列表中,存在重复的节点,删除该链表中重复的节点,重复的节点不保存,返回链表头指针


下一篇:C语言反转单向链表的代码