面试题5:从尾到头打印链表

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

分析

这道题有如下几种解决方案:

  1. 将链表逆置,然后顺次打印
  2. 递归方案
  3. 迭代方案

如果逆置链表的话,会改变链表原先的结构。我们可以在面试时询问面试过是否可以改变链表,如果是肯定的回答,就可以采用这种办法。否则只能采用后面的方法。

逆置链表也很简单,只需要从第二个节点开始,顺次摘取一个节点头插就可以。

代码如下

list* PrintListInReversedOrder(list* &head)
{
    if(head==NULL || head->next==NULL)
        return head;
    list* tmp=NULL;
    list* cur=head->next;
    head->next=NULL;
    while(cur!=NULL)
    {
        tmp=cur->next;
        cur->next=head;
        head=cur;
        cur=tmp;
    }
    cur=head;
    while(cur!=NULL)
    {
        cout<<cur->data<<" ";
        cur=cur->next;
    }
    cout<<endl;
    return head;
}

1
2
3
4
**递归方案很简单,如果当前函数参数所指向的节点是尾节点,则打印之。否则先打印它的下一个节点即可。**
### 代码如下
void PrintListInReversedOrder(list* head) { if(head==NULL) return; PrintListInReversedOrder(head->next); cout<<head->data<<" "; }
1
2
3
4
**但如果链表太长,采用递归的话可能会导致Stack OverFlow,所以更好的办法是用循环来控制。而递归在本质上就是一个栈结构(系统栈),所以我们可以用自定义的栈(数据结构栈)来模拟递归的行为以实现这种效果。**
### 代码如下
#include<stack> void PrintListInReversedOrder(list* head) { //此处不用判断head是否为空,并非忘记 stack<list*> s; list* cur=head; while(cur!=NULL) { s.push(cur); cur=cur->next; } while(!s.empty()) { cout<<s.top()->data<<" "; s.pop(); } }

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:[点我前往]()