反转链表 递归 循环

#include <stdio.h>

/*

看本程序要有的最基本大知识

1 typedef listnode *linklist(linklist是指向listnode的指针) linklist p，声明p是指向listnode的指针

2 c语言实现引用大方法

int fun(int *x,int *y)

void main()

{

int a, b;

//要想改变a，b的值

fun（&a，&b）;

}

*/

typedef char datatype;

typedef struct node{

datatype data;

struct node *next;

} listnode;

typedef listnode *linklist;//linklist是指向listnode的指针

//listnode *p;

//建立

linklist createlist(void)

{

char ch;

linklist head;

listnode *p;

head=NULL;

ch=getchar( );

while (ch!='/n'){//头插法建立链表

p=(listnode*)malloc(sizeof(listnode));

p->data=ch;

p->next=head;

head=p;

ch=getchar();

}

printf("create done/n");

return head;

}

//循环法转制链表

linklist listreverse(linklist head)

{

//方法1 允许申请空间

linklist p,rec;

p = head;

head= NULL;//头插法

do{

printf("*/n");

rec = p->next;//记录p->next的值

p->next = head;

head = p;

p = rec;

}while(p!=NULL);

return head;

}

//递归法转制链表 递归大核心思想是，把第一个看成一部分，剩余的看成一部分，把第一个转到其余的后边

linklist listreverse_recursion(struct node *pNode,linklist *head)

{

printf("******%c******/n",pNode->data);

if(pNode==NULL || pNode->next == NULL)

{

*head = pNode;

//printf("***head:%c",head->data);

return pNode;//返回最后一个节点

}

listnode *tmpNode = listreverse_recursion(pNode->next,head);

tmpNode->next = pNode;

pNode->next = NULL;

return pNode;

}

main()

{

linklist newlist = createlist();

printf("*********/n");

linklist p;

linklist q;

q = newlist;

p = newlist;

printf("建立表结果：/n");

while(q)

{

printf("*%c",q->data);

q = q->next;

}

printf("/n");

printf("反转……/n");

listreverse_recursion(newlist,&p);//c语言大引用 专门记录反转后大头指针

printf("反转完成，输出/n");

while(p)

{

printf("*%c",p->data);

p = p->next;

}

}

/*

递归方法的

结果：

abcdefg

create done

*********

建立表结果：

*g*f*e*d*c*b*a

反转……

******g******

******f******

******e******

******d******

******c******

******b******

******a******

反转完成，输出

*a*b*c*d*e*f*g

*/