输入一个链表，从尾到头打印链表每个节点的值。
链表结点定义如下：
struct ListNode { int val; ListNode* next; }; 是否能够修改链表的结构取决于面试官的需求，因此在面试的时候需要我们询问清楚面试官的要求。通常打印是个只读操作，因此这里假定不能修改链表的结构。考虑到先进后出的特性，可以使用栈来实现逆向输出。在链表操作过程在， 特别注意循环条件以及当循环结束的时候指针指向，如遍历链表时当指针指向尾结点时是否还会执行循环体中的操作如入栈操作， 非常容易出错
#include <stdio.h> #include <stdlib.h> #include <stack> #include <vector> #include <iostream> using namespace std; //当需要获取目标节点的前驱时，如增加、删除节点等操作，判断条件通常是while(p->next != NULL) //当需要获取目标节点时，如遍历节点、打印链表所有元素等操作，判断条件通常是while(p != NULL) struct ListNode { int val; ListNode* next; }; //尾插法加入元素 void Add2Tail(ListNode** pHead, int value) { ListNode *pNew = new ListNode(); pNew->val = value; pNew->next = NULL; //空链表 if (*pHead == NULL) { *pHead = pNew; } else { ListNode *pNode = *pHead; while (pNode->next != NULL) pNode = pNode->next; pNode->next = pNew; } } //按值删除节点 void RemoveNode(ListNode** pHead, int value) { if (*pHead == NULL || pHead == NULL) return; ListNode *tempNode = NULL; //头节点是要删除节点 if ((*pHead)->val == value) { tempNode = *pHead; //待删除节点 *pHead = (*pHead)->next; } else { ListNode *pNode = *pHead; //删除一个节点需要知道他的前驱，因此判断pNode->next->val,这样保证pNode指向被删节点前驱 while (pNode->next != NULL && pNode->next->val != value) pNode = pNode->next; //非尾节点且后继值等于value if (pNode->next != NULL && pNode->next->val == value) { tempNode = pNode->next; //待删除节点 pNode->next = pNode->next->next; } } if (tempNode != NULL) { delete tempNode; tempNode = NULL; } } //逆向输出链表元素 void PrintListReversingly(ListNode *pHead) { std::stack<ListNode*> list_stack; ListNode *p = pHead; if (p == NULL) return; while (p != NULL) //这里必须要用 p != NULL作判断，才能把最后一个节点入栈 { //若用 p->next != NULL,p指向尾节点时，不进行while循环体操作，少入栈一个，要么while外加一句push(p) list_stack.push(p); p = p->next; } while (!list_stack.empty()) { std::cout << list_stack.top()->val << '\t'; list_stack.pop(); } } //逆向输出vector版 vector<int> printListFromTailToHead(ListNode* head) { vector<int> result; if (head == NULL) return result; ListNode *p = head; auto it = result.begin(); while (p != NULL) { it = result.insert(it, p->val); p = p->next; } return result; } //打印链表元素 void PrintList(ListNode *head) { if (head == NULL) return; ListNode *p = head; while (p != NULL) //这里如果是p->next != NULL则不会打印最后一个结点内容 { std::cout << p->val << '\t'; p = p->next; } cout << endl; } int main() { ListNode *head = NULL; Add2Tail(&head, 67); Add2Tail(&head, 0); Add2Tail(&head, 24); Add2Tail(&head, 58); PrintList(head); PrintListReversingly(head); cout << endl; vector<int> result = printListFromTailToHead(head); for (auto i : result) cout << i << '\t'; cout << endl; system("pause"); return 0; } 本题也可以使用递归的方法，因为递归本质也是栈实现。遍历一个结点的时候，先递归输出它后面的结点，再输出自身。
//逆向输出链表元素，递归实现 void PrintListRR(ListNode *pHead) { ListNode *p = pHead; if (p == NULL) return; PrintListRR(p->next); printf("%d\t", p->val); }递归代码简洁，但是当链表非常长的时候，会导致调用函数的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码鲁棒性要好一些。
