58.从尾到头输出链表。
题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
/* 58.从尾到头输出链表。 题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; }; 1:借用栈倒序输出链表 因为栈是先进后出,把链表中的元素存进栈中,链表前面的元素在栈底,后面的元素在栈顶,链表后面的元素先出栈 2:先翻转链表,再顺序输出 就是单链表的翻转 翻转链表的步骤: 1:将当前节点的next节点指向他以前的前一个节点 2:当前节点下移一位 3:如果是最后一个节点,就把它的next节点指向它以前的前一个节点,并推出循环 3:递归实现 同栈 */ #include<iostream> #include<stdio.h> #include<string> #include<stack> using namespace std; struct node { int date; struct node *next; }; void create(node **Head,int date) { node *p=new node(); p->date=date; if(!(*Head)) { *Head=p; } else { p->next=(*Head); (*Head)=p; } } void print(node *head) { while(head) { cout<<head->date<<" "; head=head->next; } cout<<endl; } /* 方法1: 利用栈实现 */ void reverseOutput1(node* head) { node* p=head; stack<int> s; while(p!=NULL) { s.push(p->date); p=p->next; } while(!s.empty()) { printf("%d ",s.top()); s.pop(); } printf("\n"); } /* 方法2: 先链表逆序,再遍历输出 */ void reverseList(node* head) { node *p=head,*previous=NULL,*next=NULL; while(p->next!=NULL) { next=p->next;//保存下一个 p->next=previous;//p下一个为他前面的 previous=p; p=next; } p->next=previous; while(p!=NULL) { printf("%d ", p->date); p=p->next; } printf("\n"); } /* 方法3: 递归调用 */ void reverseOutput3(node* head) { if(!head) return; reverseOutput3(head->next); printf("%d ", head->date); } int main() { node *head=NULL; create(&head,9); create(&head,7); create(&head,5); create(&head,4); create(&head,3); create(&head,2); create(&head,1); cout<<"原链表数据:"<<endl; print(head); //1 2 3 4 5 7 9 cout<<"方法1: 利用栈实现 逆置结果:"<<endl; reverseOutput1(head); cout<<"方法3: 递归调用 逆置结果:"<<endl; reverseOutput3(head); cout<<endl; cout<<"方法2: 先链表逆序,再遍历输出 逆置结果:"<<endl; reverseList(head); //方法3放最后 因为把链表逆置了,或者再逆置回来 return 0; }