南阳高端网站建设,著名logo设计,WORDPRESS导购主题 WYZDG,网站建设方案doc设L为带头结点的单链表#xff0c;编写算法实现从尾到头反向输出每个节点的值。
算法思想#xff1a;
方法一#xff1a;将链表压栈再输出#xff0c;时间复杂度为O(n),空间复杂度为O(n)
方法二#xff1a;用头插法重新建立单链表在输出#xff0c;时间复杂度为O(n),空…设L为带头结点的单链表编写算法实现从尾到头反向输出每个节点的值。
算法思想
方法一将链表压栈再输出时间复杂度为O(n),空间复杂度为O(n)
方法二用头插法重新建立单链表在输出时间复杂度为O(n),空间复杂度为O(1)
方法三用递归本质上也用到了栈所以空间复杂度为O(n),时间复杂度为O(n)
代码
#includeiostream
#includeinitList/initList.h
#includestack
using namespace std;// 方法一用栈
void reversePrint(LinkList* L){stackTypeData s;//压栈while(L-next !NULL ){ s.push(L-next-data);L L-next;}//打印while(!s.empty()){couts.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){coutL-data ;}
}int main(){LinkList* L initList();//方法一reversePrint(L);// 方法二headInPrint(L);//方法三recur(L-next);
}
