C语言递归，非递归实现翻转链表

翻转链表作为，链表的常用操作，也是面试常遇到的。

分析
非递归分析：

非递归用的小技巧比较多，很容易出错。

递归分析比较简单，在代码里面

代码：

#include<stdio.h>
#include<stdlib.h>
typedef int elemtype;
typedef struct node{
    elemtype element;
    struct node*next;//写成node* next;node * next;node *next;也是可以的，为了方便阅读，以后统一写成elemtype* element。'*',';',',''=','->'等等这些特殊意义的关键字符语法规则差不多，本身具有分割意义，两旁加空格与不加空格的意义是一致的，也就是说空格对这些特殊字符是不起作用的，而解析编译器，运行器也不是利用空格来分割的；标志符是不能用这些字符，为了方便阅读，不会看的一驼屎，最好在这些特殊的字符两旁加空格。
}node;//这个类型名与其的结构体名可以一样，不矛盾。

/*Function:将链表所有结点从头结点顺序打印，遍历链表。traverse_linkedList
 *遍历一种数据机构，进去看一看，给人说一说,一般遍历打印里面的数据，知道是进去，可以拿到里面的数据。
 *这种数据结构有很多数据元素，但每次遍历只能访问一个元素，因此要循环，而且要访问所有的结点，必须有一种机制从一个结点跳到另一个结点。
 *@paramb:node* phead :链表首地址，首结点地址。
 */
void traverse_linkedList(node* phead){
    node *p=phead ;//定义一个跳转控制指针
    if (NULL == p){
        printf("亲，链表为空\n");
        return ;
    }
    else{
        while(NULL !=  p){

        printf("%d\n",p -> element);//访问结构体的数据，可以用: 其结构体变量.成员变量；还可以:指向这个结构体的指针 -> 成员变量
        p = p -> next ;
        }    
    }

}
/*Function:翻转链表(非递归) reverse_linkedList
 *param:node** phead  //参数意义：保存链表指针变量的地址
 *return: void
 *
 *知识点：node** p;p代表链表指针变量的地址。*p才是链表。**p 代表结点（可以认为"*"具有解析功能）
 *整体的思路：重整结点的关系，原来从左指向右，翻转后从右指向左；原来指向头结点，翻转后指向尾结点
 *
 *时间复杂度：O(n)
 *
 *
 * */
void reverse_linkedList(node** phead){//存链表头的指针变量的地址传过来，旨在能改变这个变量，指针本质上是存地址的变量。
    node *pLeft,*pRight,*pMiddle;//定义三个指针: 左中右,pRight:作移动。
    pLeft=pRight=*phead;
    //空链表或者只有一个结点
    if(NULL == pLeft || NULL == ( pLeft -> next)){
            return ;
    
    }else{
        //头的结点的处理
        pLeft = *phead ;
            pRight = (*phead) -> next ; //' ->'优先级最高
        pLeft -> next = NULL ;

        //循环控制条件    
            node *ctl=pRight;
         while(NULL != ctl){
            pMiddle = pRight ;// 在移动前，先保存
            pRight = pRight -> next ;// pRight移动到下一个结点
            ctl = pMiddle -> next; //在变换关系前，先把控制的信息存起来 
            pMiddle -> next = pLeft ; //变换关系
            pLeft = pMiddle ; // p变换    
        }
        
        *phead = pLeft ; //指向链表头指针变量，指向新的头。
    }
}
/*
 *Function:翻转链表(递归) reverse_recursive_linkedList
 *param:node* head  
 *return: node*
 *
 *知识点：
 *递归：自身调用自身；出口。
 *思考：
 *
 *如果链表是空链表或者只有一个结点，就可以直接的返回表头；如果是两个结点以上链表，调用自身，拿到子结点的表头，再重建他们的关系。
 *
 * */
node* reverse_recursive_linkedList(node * head){
    if(head == NULL || head -> next == NULL){
       return head ; 
    }
    else{
       node* second = head -> next ;
       node* new_head = reverse_recursive_linkedList(second);
       second -> next = head ;
       head -> next = NULL ;
       return new_head ;       
    } 
}
int main()
{
    node *p , *q , *head;//仅仅定义了几个指针变量，系统做了哪些工作呢？开辟这些指针变量类型所需的空间。若没有初始值一般由系统随机分配值，还没有指向真正的结点，也就是说 p -> 成员变量是没有意义的。会报""; node 类型的声明，告诉系统作对应的语法检查，该怎么处理指针指向的内容。
    // insert 10 nodes
    //创建结点，结点本质上是数据块，这些数据是占用空间的，有了储存空间，就有了数据载体。所以开辟空间是创建数据的关键，然后告诉系统你怎么来处理这块空间，最后空间开辟成功。
    p = q = (node* )malloc(sizeof(node)) ;//与” 数据类型 标识符“ 创建的差别，无标识符，要手动开空间,并提取信息。标识符功能：解析+地址。
    head = p ;
    p -> element = 0 ;
    int i=0;
    for ( i = 0 ;i < 9 ; i++){
        
        q = (node* )malloc(sizeof(node)) ;
        q -> element = i + 1 ;
        p -> next = q ;
        p = q ;


    }
    

    traverse_linkedList(head);
    reverse_linkedList(&head);//&只能作取址用，没有解析功能。
    traverse_linkedList(head);
    traverse_linkedList(reverse_recursive_linkedList(head));
}

本人在重拾C，很多东西看是熟悉而又陌生，所以注释比较多一点，仅供参考，不爽直接忽略，