写一个CC++程序，实现链表的逆序。

假设链表为a->b->c->d

逆序后为d->c->b->a

#include <stdio.h>

#include <stdlib.h>

typedef int Type

typedef struct Node{

Type data

struct Node *next

}Node

void insert(Type data,Node **head){//插入一个节点

Node *tmp = (Node*)malloc(sizeof(Node))

tmp->next=*head

tmp->data=data

*head=tmp

}

void print_list(Node *head){//打印链表

Node *tmp=head

while(tmp){

printf("%d ", tmp->data)

tmp=tmp->next

}

printf("\n")

}

void revert_list(Node **head){//翻转链表

if(!*head)//空链表，无需翻转

return

Node *p=NULL,//前一个节贺卖点

*c=*head,//当前节点

*n=(*head)->next//下一个节点

while(n){//如果没有到链表尾部冲雹

c->next=p//逆序当前节点

p=c//节点前进

c=n//节点前进

n=n->next//节点前进

}

c->next=p

*head=c

}

int main(){

Node *head=NULL

int a[5]={1,2,3,4,5}

for(int i=0i<5i++)

insert(a[i],&head)

print_list(head)//反序前输散拍帆出

revert_list(&head)//反序

print_list(head)//反序后输出

return 0

}

这道题，是我毕业前在北京找实习真实碰到的一个面试题。

逆序谁不会是吧，啥？不能用数组，不能用字符串，集合。只能用node自己构建链表竖旦。

嗯，好像有点儿印象，大学学数据结构的时候都学过。

但是那会儿真是全忘了，面试官很有耐心，还教了我。唉。：）

分三步，第一步先实现链表，第二步顺序打印，第三步逆序打印，逆序打印这里有两种方案。1. 链表反转，顺序打印。2. 链表余悔扰不动，逆序打印

add方法要点：

顺序就是用while输出value就行，逆序就是写个递归倒着输出value就行

重点说一下我做反转链表的思路

所有思路都在图片里面了。

PS：这应该是我最后一次主动在网上画图前枯，太费劲儿了，以后还是手画。

循环链表，把头尾接走来就行

tail->next = head

判定是否到达尾部，1.设置计数；2.判断下一个指针是否是head

逆序输出

1.重新开辟空间，芦吵建立逆序链表

2.建立双向链表，即增加 pre指针指向前一个

3.如果只是要逆序输出，调用递归算法

逆序输出( 链表 )

{

if 下一个是否为空唯绝

输出

else

逆序输出( next )

end

输指哗姿出

}

---