方法一
实现链表翻转最直接的方法就是：从链表的头部开始遍历每个结点，改变每个结点的指向，即将原本指向下一个结点的指针改为指向上一个结点。
遍历原链表，将结点依次插入到新链表的头部。要完成这一步操作，我们需要新添加两个指针（分别命名为 P 和 tmp）：
- P 指针用于遍历链表，并将遍历到的结点插入到新链表中；
- tmp 指针永远指向指针 P 所在结点的下一个结点，充当原链表在每次移除头部结点后的新头指针；
List * reverse(List * H) { if(H == NULL || H->next == NULL) { return H; } List *p = H; //创建指针p作为遍历链表的指针 List *newH = NULL; //创建新链表，用于存储反转的链表 while(p != NULL) { List *tmp = p->next; p->next = newH; newH = p; p = tmp; } return newH; }
方法二
另一种方法较前一种比较复杂，需要使用到递归的思想。
方法一是依次遍历链表，更改每个结点的指向，最后一个结点为翻转链表的头部结点。而方法二则完全倒过来，其实现过程为：先通过递归的思维找到链表的头部，然后再改变每个结点的指向，最终到达链表翻转的目的。
//链表翻转的函数 link *reverseList(link * H){ //如果指针 H 是否存在 if(H == NULL || H->next == NULL){ return H; } //递归查找新链表的头，找到用赋值给 newH link * newH=reverseList(H->next); //递归完成后，H 初始状态为 NewH 的上一个结点。 //在一步步弹栈的过程中，始终另 H 指向的结点作为新链表的最后一个结点 H->next->next=H; //在链接到新链表之后，要割去 H 所指结点与下一结点的联系，否则会使新链表产生环 H->next=NULL; //返回新链表所指头部的指针。 return newH; }
