链表逆序是个很基础的算法，考察的是指针操作和基本数据结构。常规的写法当然是OK的，不过要是还会写出一个递归的链表逆序算法，那别人肯定要给你点个赞了。

1 问题描述

给定一个链表，请将其逆序。即如果链表原来为1->2->3->4->5->null，逆序后为5->4->3->2->1->null.

2 常规写法(迭代)

迭代算法效率较高，但是代码比递归算法略长。递归算法虽然代码量更少，但是难度也稍大，不细心容易写错。迭代算法的思想就是遍历链表，改变链表节点next指向，遍历完成，链表逆序也就完成了。代码如下：

struct node {
    int data;
    struct node* next;
};
typedef struct node* pNode;

pNode reverse(pNode head)
{
    pNode current = head;
    pNode next = NULL, result = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = result;
        result = current;
        current = next;
    }
    return result;
}

如果不返回值，可以传递参数改为指针的指针，直接修改链表的头结点值（如果在C++中直接传递引用更方便），可以写出下面的代码：

void reverse(pNode* headRef)
{   
    pNode current = *headRef;
    pNode next = NULL, result = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = result;
        result = current;
        current = next;
    }
    *headRef = result;
}

3 进阶写法(递归)

递归写法的实现原理：假定原链表为1，2，3，4，则先逆序后面的2，3，4变为4，3，2，然后将节点1链接到已经逆序的4，3，2后面，形成4，3，2，1，完成整个链表的逆序。代码如下：

void reverseRecur(pNode* headRef)
{
    if (*headRef == NULL)  return;
    pNode first, rest;
    first = *headRef;      
    rest = first->next;   
    if (rest == NULL) return;
    reverseRecur(&rest); 
    first->next->next = first; //注意这里不要错写成rest->next = first噢，请想想指针的指向。
    first->next = NULL;
    *headRef = rest;  //更新头结点
}

如果使用C++的引用类型，代码会稍显简单点，代码如下：

void reverseRecur(pNode& p)
{
    if (!p) return;
    pNode rest = p->next;
    if (!rest) return;
    reverseRecur(rest);
    p->next->next = p;
    p->next = NULL;
    p = rest;
}

参考资料

leetcode的链表某一节的题目，具体链接找不到了，请见谅