EEPW论坛

单链表反转

原理：波切尔函数？

比如原链表为 head->1->2->3->NULL; 
反转后：head->3->2->1->NULL;

1. #include <stdio.h>  

2. #include <stdlib.h>  

3. typedef struct Node  

4. {  

5.     int data;  

6.     struct Node *next;  

7. }*List;  

8.   

9. #define node struct Node  

10.   

11. List creat(void);  

12. List re( List head ,List p,List q);  

13. void Outlist( List q );  

14.   

15. int main(int argv, char *argc[])  

16. {  

17.     List head;  

18.     List p;  

19.     List q;  

20.     head = NULL;  

21.     head = creat();  

22.     p = head->next;  

23.     q = head;  

24.     re(head,p,q);  

25.     q = head->next;  

26.     Outlist(q);  

27.     system("pause");  

28.   

29.     return 0;  

30. }  

31.   

32. List creat(void)  

33. {  

34.     int data;  

35.     List head;  

36.     List p;  

37.     List q;  

38.     int flag = 1;  

39.     head = (List)malloc(sizeof(node));  

40.     q = head;  

41.     do  

42.     {  

43.         printf("请输入正数(<MAX_INT输入0表示输入结束)：");  

44.         scanf("%d",&data);  

45.         fflush(stdin);  

46.         if ( 0 == data )  

47.         {  

48.             q->next = NULL;  

49.             flag = 0;  

50.         }  

51.         else  

52.         {  

53.             p = (List)malloc(sizeof(node));  

54.             p->data = data;  

55.             q->next = p;  

56.             q = p;  

57.         }  

58.     }while(flag);  

59.     q = head->next;  

60.     Outlist(q);  

61.     return head;  

62. }  

63.   

64. void Outlist( List q )  

65. {  

66.     while(NULL != q)  

67.     {  

68.         printf("%d ",q->data);  

69.         q = q->next;  

70.     }  

71.     printf("\n");  

72.     return;  

73. }  

74.   

75. List re(List head,List p,List q)  

76. {  

77.     if(NULL == p)  

78.     {  

79.         head->next = q;  

80.     }  

81.     else  

82.     {  

83.         p=re(head,p->next,q->next);  

84.         p->next = q;  

85.         if( head ==  q)  

86.         {  

87.             p->next = NULL;  

88.         }  

89.     }  

90.     return q;  

91. }