链表反转
创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站建设、成都网站制作、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的江苏网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1-2-3-4-5 通过反转后成为5-4-3-2-1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct linka {
int data;
linka* next;
};
void reverse(linka* head)
{
if(head ==NULL)
return;
linka*pre, *cur, *ne;
pre=head;
cur=head-next;
while(cur)
{
ne = cur-next;
cur-next = pre;
pre = cur;
cur = ne;
}
head-next = NULL;
head = pre;
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
linka* reverse(linka* p,linka* head)
{
if(p == NULL || p-next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p-next,head);
tmp-next = p;
return p;
}
}
void reverse()
{
Node *prev,*current;
prev=head; //从头结点开始处理
if(head==NULL) return;
for(current=prev-next;current!=NULL;current=current-next) //顺序处理结点
{
current-next=prev; //下一个结点的next指点上一个结点，即将链表反转
prev=current; //保存上一个结点
}
head=prev; //head为最后一个结点
}
单链表反转：
比如原链表为 head-1-2-3-NULL;
反转后：head-3-2-1-NULL;
实现代码：
#include stdio.h
#include stdlib.h
typedef struct Node
{
int data;
struct Node *next;
}*List;
#define node struct Node
List creat(void);
List re( List head ,List p,List q);
void Outlist( List q );
int main(int argv, char *argc[])
{
List head;
List p;
List q;
head = NULL;
head = creat();
p = head-next;
q = head;
re(head,p,q);
q = head-next;
Outlist(q);
system("pause");
return 0;
}
List creat(void)
{
int data;
List head;
List p;
List q;
int flag = 1;
head = (List)malloc(sizeof(node));
q = head;
do
{
printf("请输入正数(MAX_INT输入0表示输入结束)：");
scanf("%d",data);
fflush(stdin);
if ( 0 == data )
{
q-next = NULL;
flag = 0;
}
else
{
p = (List)malloc(sizeof(node));
p-data = data;
q-next = p;
q = p;
}
}while(flag);
q = head-next;
Outlist(q);
return head;
}
void Outlist( List q )
{
while(NULL != q)
{
printf("%d ",q-data);
q = q-next;
}
printf("\n");
return;
}
List re(List head,List p,List q)
{
if(NULL == p)
{
head-next = q;
}
else
{
p=re(head,p-next,q-next);
p-next = q;
if( head == q)
{
p-next = NULL;
}
}
return q;
}
2.写一个算法，借助栈将一个带头结点的单链表倒置。
要求：利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的data域的值依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到链表的每个结点的data域中。
#includestdio.h
#includestdlib.h
#includemalloc.h
#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
typedef int ElemType;
typedef struct link
{
int data;
struct link *next;
}NODE;
NODE *creast(int n)
{
NODE *head,*q,*p;
int i=1;
head=(NODE*)malloc(sizeof(NODE));
if(head)
{
printf("input the %dth number:",i);
scanf("%d",head-data);
head-next=NULL;
p=head;
}
else
exit(0);
while(in)
{
q=(NODE*)malloc(sizeof(NODE));
q-next=NULL;
printf("input the %dth number:",++i);
scanf("%d",q-data);
p-next=q;
p=q;
}
return head;
}
void output(NODE *head)
{
NODE *p;
p=head;
do
{
printf("%d",p-data);
p=p-next;
}while(pprintf("--"));
printf("\n");
}
int InitStack(SqStack S)
{
int size = STACK_INIT_SIZE;
S.base=(int *)malloc(size*sizeof(ElemType));
if(!S.base)
return 0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}
int Push(SqStack S, int e)
{ if(S.top-S.base=S.stacksize)
{
int stackinvrement = STACKINCREMENT;
S.base=(ElemType *) realloc(S.base,(S.stacksize+stackinvrement)*sizeof(ElemType));
if(!S.base)
return 0;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}
int OutputStack(SqStack S)
{
return *--S.top;
}
void main()
{
int n,i;
SqStack s;
NODE *head,*p;
InitStack(s);
printf("请输入要进栈的元素个数是:");
scanf("%d",n);
p=head=creast(n);
output(head);
for(i=1;i=n;i++)
{
Push(s,p-data);
p=p-next;
}
p=head;
for(i=1;i=n;i++)
{
p-data=OutputStack(s);
p=p-next;
}
output(head);
}
单链表反转很简单，只说下思路：
1，从头到尾循环遍历链表
2，取下头结点，作为尾结点，尾结点此时也为头结点
3，采用前插法，将步骤二中取下的结点一个一个连接到头结点前面，成为新的头结点。
4，链表全部遍历完后，新的链表产生了，是原来链表的反转。
