算法之线性表1.1.1（7）带头结点链表的反向输出

设L为带头结点的单链表，编写算法实现从尾到头反向输出每个节点的值。

算法思想：

方法一：将链表压栈再输出，时间复杂度为O(n),空间复杂度为O(n)

方法二：用头插法重新建立单链表在输出，时间复杂度为O(n),空间复杂度为O(1)

方法三：用递归，本质上也用到了栈，所以空间复杂度为O(n),时间复杂度为O(n)

代码：

#include<iostream>
#include"initList/initList.h"
#include<stack>
using namespace std;// 方法一：用栈
void reversePrint(LinkList* L){stack<TypeData> s;//压栈while(L->next !=NULL ){ s.push(L->next->data);L = L->next;}//打印while(!s.empty()){cout<<s.top()<<" ";s.pop();}
}
//方法二：用头插法
void headInPrint(LinkList* L){LinkList *p;p = L->next;L->next = NULL;while(p!=NULL){LinkList* temp = (LinkList*)malloc(sizeof(LinkList*));//保持不断链temp = p->next;//头插法p->next = L->next; //p节点指向node2L->next = p;p = temp;}printList(L);
}方法三:用递归
void recur(LinkList* L){if(L->next!=NULL){recur(L->next);}if(L!=NULL){cout<<L->data<<" ";}
}int main(){LinkList* L = initList();//方法一：reversePrint(L);// 方法二：headInPrint(L);//方法三：recur(L->next);
}