从尾到头打印单向链表

需求：

给定一个单项链表的头结点，从尾到头打印链表中的节点的值。

分析：

思路一

由于从链表的结尾开始逆序打印，也就是说最后的节点先打印，联想到后进先出，可以使用栈来依次把链表节点保存起来，然后从新栈顶开始获取节点打印并且把节点出栈，直到栈为空，打印结束。见示例代码reversePrintByStack。

思路二

由于打印的思想跟栈类似，可以进一步联想到函数调用保留现场也是通过栈的方式实现的，因此可以考虑使用递归来实现，如果当前节点后面还有节点，则查找后面的节点，等找到后面节点返回了，再打印当前节点。如果当前节点后面没有节点了，就直接打印当前节点的值。见示例代码reversePrintByRecursion。

c++实例代码

  1 #include <iostream>
  2 #include <stack>
  3 
  4 using namespace std;
  5 
  6 //单链表节点
  7 struct ListNode {
  8     //节点存储的数字
  9     int m_nValue;
 10     //下一个节点的指针
 11     ListNode* m_pNext;
 12 };
 13 
 14 /************************************************************************/
 15 /* @brif 在链表结尾增加节点
 16 /* @param pHead 链表头结点
 17 /* @param value 要增加的节点值
 18 /************************************************************************/
 19 void AddNodeToTail(ListNode** pHead, int value)
 20 {
 21     ListNode *addNode = new ListNode;
 22 
 23     if (!addNode)
 24     {
 25         cout << "add node fail!!!" << endl;
 26         return;
 27     }
 28     addNode->m_nValue = value;
 29     addNode->m_pNext = nullptr;
 30 
 31     //头结点为空的情况,新增加的节点作为头结点
 32     if (!*pHead)
 33     {
 34         *pHead = addNode;
 35     }
 36     //头结点不为空的情况，查找到最后一个节点，修改最后一个节点的指向
 37     else
 38     {
 39         ListNode* tmpNode = *pHead;
 40         //找到最后一个头结点
 41         while (tmpNode->m_pNext)
 42         {
 43             tmpNode = tmpNode->m_pNext;
 44         }
 45         tmpNode->m_pNext = addNode;
 46     }
 47 }
 48 
 49 /************************************************************************/
 50 /* @brif 打印链表中的节点
 51 /* @param pHead 链表头结点
 52 /************************************************************************/
 53 void printLinkList(ListNode* pHead)
 54 {
 55     ListNode* currNode = pHead;
 56 
 57     if (!currNode)
 58     {
 59         cout << "空链表" << endl;
 60     }
 61 
 62     while (currNode)
 63     {
 64         cout << currNode->m_nValue << "->";
 65         currNode = currNode->m_pNext;
 66     }
 67     cout << "结束" << endl;
 68 }
 69 
 70 /************************************************************************/
 71 /* @brif 删除链表中的所有节点
 72 /* @param pHead 链表头结点
 73 /************************************************************************/
 74 void removeAllNode(ListNode** pHead)
 75 {
 76     ListNode* currNode = *pHead;
 77 
 78     if (!*pHead)
 79     {
 80         cout << "空链表" << endl;
 81     }
 82 
 83     ListNode* delNode = nullptr;
 84     while ((*pHead)->m_pNext)
 85     {
 86         delNode = (*pHead);
 87         (*pHead) = (*pHead)->m_pNext;
 88         delete delNode;
 89         delNode = nullptr;
 90     }
 91     delete (*pHead);
 92     *pHead = nullptr;
 93 }
 94 
 95 /************************************************************************/
 96 /* @brif 使用栈逆序打印链表
 97 /* @param pHead 链表头结点
 98 /************************************************************************/
 99 void reversePrintByStack(ListNode* pHead)
100 {
101     if (!pHead)
102     {
103         cout << "空链表" << endl;
104     }
105     
106     stack<ListNode*> listStack;
107     ListNode* tmpNode = pHead;
108     
109     //依次把链表中的节点放到栈中
110     while (tmpNode->m_pNext)
111     {
112         listStack.push(tmpNode);
113         tmpNode = tmpNode->m_pNext;        
114     }
115     //把最后一个节点也加入到栈中
116     listStack.push(tmpNode);
117 
118     //如果栈不为空，则打印最上面的节点，然后出栈
119     while (!listStack.empty())
120     {
121         cout << (listStack.top())->m_nValue << "	";
122         listStack.pop();
123     }
124 }
125 
126 /************************************************************************/
127 /* @brif 使用递归的方法逆序打印链表
128 /* @param pHead 链表头结点
129 /************************************************************************/
130 void reversePrintByRecursion(ListNode* pHead)
131 {
132     if (!pHead)
133     {
134         cout << "空链表" << endl;
135     }
136 
137     if (pHead->m_pNext)
138     {
139         reversePrintByRecursion(pHead->m_pNext);
140         cout << pHead->m_nValue << "	";
141     }
142     else
143     {
144         cout << pHead->m_nValue << "	";
145     }
146 }
147 
148 int main()
149 {
150     ListNode* pHead = nullptr;
151 
152     cout << "原始链表:" << endl;
153     //创建链表
154     for (int i = 1; i <= 10; ++i)
155     {
156         AddNodeToTail(&pHead, i);        
157     }
158     printLinkList(pHead);
159 
160     cout << endl <<"通过栈逆序打印链表:" << endl;
161     reversePrintByStack(pHead);
162 
163     cout << endl << "通过递归的方法逆序打印链表" << endl;
164     reversePrintByRecursion(pHead);
165 
166     removeAllNode(&pHead);
167 
168     cout << endl;
169 
170     return 0;
171 }

从尾到头打印单向链表

需求：

分析：

思路一

思路二

c++实例代码

运行结果