首页 > 代码库 > 算法题之二(从尾到头打印链表)
算法题之二(从尾到头打印链表)
链表节点定义如下：
1 typedef struct ListNode2 {3 int value;4 ListNode *next;5 }TListNode;
众所周知，链表打印时从头到尾很简单，所以我们首先想到的可能是先把链表逆序，然后从头到尾再打印出来即可，但是逆序会破坏链表的结构，对于打印操作来说仅仅是读操作而已，如果破坏了链表结构似乎不和常理，哪么我们是否有更好的解决办法呢？答案是肯定的。
我们知道要解决该问题肯定需要遍历链表，而第一个遍历的节点需要最后一个打印出来，而最后一个遍历的节点需要最先被打印出来，这是一个很典型的“后入先出”，我们能很迅速的想到用栈来解决该问题，我们只需要在遍历时依次将结点压入栈中，再从栈顶依次输出每个结点的值即达到目的。这种思路实现代码如下：
1 void PrintListReversing(TListNode *head) 2 { 3 stack<TListNode*> nodes; 4 5 TListNode *pnode = head; 6 while (NULL != pnode) 7 { 8 nodes.push(pnode); 9 10 pnode = pnode->next;11 }12 13 while (!nodes.empty())14 {15 pnode = nodes.top();16 17 cout << pnode->value << endl;18 19 nodes.pop();20 }21 }
既然想到用栈来实现，而递归本身就是一个栈结构，因而不难想出用递归的方式来实现，实现代码如下所示：
1 void PrintListReversing2(TListNode *head) 2 { 3 if (NULL != head) 4 { 5 if (NULL != head->next) 6 { 7 PrintListReversing2(head->next); 8 } 9 10 cout << head->value << endl;11 }12 }
上面的实现代码非常简洁，但是如果链表中结点数很多，可能会导致函数栈溢出，因此实际编码中应该避免使用。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。