剑指offer-面试题5.从尾到头打印链表-白红宇

剑指offer-面试题5.从尾到头打印链表

阅读量：6085 次

发布时间：2019-06-20

本文共 2846 字，大约阅读时间需要 9 分钟。

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

刚看到这道题的小伙伴可能就会想，这还不简单，将链表反转输出。

但是这种情况破坏了链表的结构。

如果面试官要求不破坏链表结构呢，这时候我们就想到了一种数据

结构---栈当我们从前往后遍历链表逐个压栈然后遍历结束后再

逐个出栈。

首先我们先来用第一种方式实现:

1 #include 
     
       2 using namespace std; 3  4 struct ListNode 5 { 6     int data; 7     struct ListNode *next; 8 }; 9 10 struct ListNode* CreateList()11 {12     struct ListNode* Head,*p;13     Head=(struct ListNode*)malloc(sizeof(ListNode));14     Head->data=0;15     Head->next=NULL;16     p=Head;17 18     cout<<"Create List....(0-exit!)"<
      
       >Data;23         if(Data!=0)24         {25             struct ListNode* NewNode;26             NewNode=(struct ListNode*)malloc(sizeof(ListNode));27             NewNode->data=Data;28             NewNode->next=NULL;29             p->next=NewNode;30             p=p->next;31         }32         else33         {34             break;35         }36     }37 38     return Head->next;39 }40 41 void PrintList(struct ListNode* Head)42 {43     cout<<"The List is: ";44 45     struct ListNode *p;46     p=Head;47     while(p!=NULL)48     {49         cout<
       
        data<<" ";50         p=p->next;51     }52     cout<
        
         next;61 62     while(p2!=NULL)63     {64         p3=p2->next;65         p2->next=p1;66         p1=p2;67         p2=p3;68     }69 70     Head->next=NULL;71     return p1;72 }73 74 int main()75 {76     ListNode *Head,*NewHead;77     Head=CreateList();78     PrintList(Head);79     NewHead=ReversePrint(Head);80 81     cout<
         
          <<"The Reverse List is:"<

截图:

注意:这种情况下是破坏了链表的结构了。

下面我们用栈结构来实现不破链表本身结构的逆序输出:

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 struct ListNode 6 { 7     int data; 8     struct ListNode *next; 9 };10 11 struct ListNode* CreateList()12 {13     struct ListNode* Head,*p;14     Head=(struct ListNode*)malloc(sizeof(ListNode));15     Head->data=0;16     Head->next=NULL;17     p=Head;18 19     cout<<"Create List....(0-exit!)"<
       
        >Data;24         if(Data!=0)25         {26             struct ListNode* NewNode;27             NewNode=(struct ListNode*)malloc(sizeof(ListNode));28             NewNode->data=Data;29             NewNode->next=NULL;30             p->next=NewNode;31             p=p->next;32         }33         else34         {35             break;36         }37     }38 39     return Head->next;40 }41 42 void PrintList(struct ListNode* Head)43 {44     cout<<"The List is: ";45 46     struct ListNode *p;47     p=Head;48     while(p!=NULL)49     {50         cout<
        
         data<<" ";51         p=p->next;52     }53     cout<

S;62 63 while(p!=NULL)64 {65 S.push(p->data);66 p=p->next;67 }68 69 cout<<"Reverse To Print LinkList: ";70 while(!S.empty())71 {72 cout<

<<" ";73 S.pop();74 }75 76 cout<

截图: