题解 | #反转链表#(指针数组法，迭代法，递归法)

建立一个指针数组，先遍历一遍链表，在遍历时将指向每一个节点的指针存入指针数组中，并找到最后一个节点记作wei。最后，以wei为头节点在反向输出这个数组为p->next赋值，以创建一个反向的链表。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead )
{
    if(pHead==NULL)
        return pHead;
    struct ListNode* cout[1000];
    int i=0;
    struct ListNode* p=pHead;
    struct ListNode* wei=NULL;
    while(p->next!=NULL)
    {
        cout[i++]=p;
        p=p->next;
    }
    wei=p;
    i=i-1;
    while(i>=0)
    {
        p->next=cout[i--];
        p=p->next;
    }
    p->next=NULL;
    return wei;
}

利用三个指针进行迭代。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead )
{
    struct ListNode *cur=pHead;
    struct ListNode *newhead=NULL;
    struct ListNode *next;
    cur=pHead;//cur指向现在正在处理的节点
    newhead=NULL;//newhead指向正在处理的节点的上一个节点
    while(cur!=NULL)
    {
        next=cur->next;//next指向cur的下一个节点
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

递归法

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead )
{
    if(pHead==NULL||pHead->next==NULL)
    return pHead;
    struct ListNode * newhead=ReverseList(pHead->next);
    pHead->next->next=pHead;
    pHead->next=NULL;
    return newhead;
}

执行到struct ListNode *newhead=ReverseList(pHead->next);

时，程序被编译器记录进入栈的位置，并且开始进栈（递归中的递），程序从头开始，每一次到struct ListNode *newhead=ReverseList(phead->next);

时，重复之前的操作，直到最深处——

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

return pHead;

符合if语句条件，pHhead被返回出来了具体的值——5，于是程序开始出栈（递归中的归），返回到上一层此时pHead=4。由于程序记录了进栈的位置，出栈时就从进栈的下一句开始执行——执行pHead->next->next=pHead;

pHead->next=NULL;

return newhead;

这三句。newhead在执行这三句时没有被操作，所以值不变。每重复一边这三句话pHead的值就减少1。