从尾到头打印单向链表

本文主要是介绍从尾到头打印单向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.需求及分析

输入一个链表的头结点，从尾到头反过来打印出每个节点的值。

方法：

1.把链表中链接节点的指针反转过来，改变链表的方向，然后从头到尾输出。（实际上修改了链表的结构下下策）；

2.典型的先进后出，可以用“栈”处理；

3.典型的先进后出，由于递归和栈的处理方式接近也可以用递归处理。

2.使用栈处理

void PrintListReversingly_Iter(ListNode* pHead)
{std::stack<ListNode*> nodes; //定义链表指针栈区ListNode* pNode = pHead;     // 链表首地址指针while (pNode != NULL) //终止条件：链表地址指针为空{nodes.push(pNode);       //链表首地址指针压入栈区pNode = pNode->next;     //取下一个指针}while (!nodes.empty()) //终止条件：栈区为空{pNode = nodes.top();             //弹出链表指针cout << pNode->value<<"       "; //取出索引值nodes.pop();}
}

3.等效递归处理

void PrintListReversingly_Recur(ListNode* pHead)
{if (pHead != NULL){if (pHead->next != NULL){PrintListReversingly_Recur(pHead->next);}cout << pHead->value << "       "; }
}

4.测试代码

/* list.h */
#include <stdio.h>  
#include <stdlib.h>  struct ListNode{int value;ListNode* next;
};ListNode* CreateListNode(int value){ListNode* pNode = new ListNode();pNode->value = value;pNode->next = NULL;return pNode;
}void ConnectListNode(ListNode* pCurrent, ListNode* pNext){if (pCurrent == NULL){printf("Error to connect two nodes.\n");exit(1);}pCurrent->next = pNext;
}void PrintListNode(ListNode* pNode){if (pNode == NULL)printf("The node is null.\n");elseprintf("The key in node is %d.\n", pNode->value);
}void PrintList(ListNode* pHead){ListNode* pNode = pHead;while (pNode){printf("%d\t", pNode->value);pNode = pNode->next;}printf("\n");
}void DestroyList(ListNode* pHead){ListNode* pNode = pHead;while (pNode){ListNode* pNext = pNode->next;delete pNode;pNode = pNext;}
}void AddToTail(ListNode** pHead, int value){ListNode* pNode = new ListNode();pNode->value = value;pNode->next = NULL;if (*pHead == NULL)*pHead = pNode;else{ListNode* pCurrent = *pHead;while (pCurrent->next)pCurrent = pCurrent->next;pCurrent->next = pNode;}
}void RemoveHead(ListNode** pHead, int value){if (pHead == NULL || *pHead == NULL)return;ListNode* pToBeDeleted = NULL;if ((*pHead)->value == value){pToBeDeleted = *pHead;*pHead = (*pHead)->next;}else{ListNode* pNode = *pHead;while (pNode->next != NULL && pNode->next->value != value)pNode = pNode->next;if (pNode->next != NULL && pNode->next->value == value){pToBeDeleted = pNode->next;pNode->next = pNode->next->next;}}if (pToBeDeleted != NULL){delete pToBeDeleted;pToBeDeleted = NULL;}
}

/* PrintReversingly */
#include <iostream>
#include "list.h"
#include <stack>
using namespace std;void PrintListReversingly_Iter(ListNode* pHead)
{std::stack<ListNode*> nodes; //定义链表指针栈区ListNode* pNode = pHead;     // 链表首地址指针while (pNode != NULL) //终止条件：链表地址指针为空{nodes.push(pNode);       //链表首地址指针压入栈区pNode = pNode->next;     //取下一个指针}while (!nodes.empty()) //终止条件：栈区为空{pNode = nodes.top();             //弹出链表指针cout << pNode->value<<"       "; //取出索引值nodes.pop();}
}void PrintListReversingly_Recur(ListNode* pHead)
{if (pHead != NULL){if (pHead->next != NULL){PrintListReversingly_Recur(pHead->next);}cout << pHead->value << "       "; }
}
void Results(ListNode* pHead)
{PrintList(pHead);cout << endl;PrintListReversingly_Iter(pHead);cout << endl;PrintListReversingly_Recur(pHead);
}void Test1()
{cout << endl;cout << "Test1 begins:" << endl;ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(2);ListNode* pNode3 = CreateListNode(3);ListNode* pNode4 = CreateListNode(4);ListNode* pNode5 = CreateListNode(5);ConnectListNode(pNode1, pNode2);ConnectListNode(pNode2, pNode3);ConnectListNode(pNode3, pNode4);ConnectListNode(pNode4, pNode5);Results(pNode1);DestroyList(pNode1);
}int main()
{Test1();return 0;
}

这篇关于从尾到头打印单向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---