题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）

题解

迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        register ListNode *prev = NULL;
        register ListNode* curr = head;
        register ListNode* temp;
        while (curr != NULL) {
            temp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = temp;
        }
        return prev;
    }
};

结果

执行用时 : 16 ms, 在所有 C++ 提交中击败了53.05%的用户
内存消耗 : 9.2 MB, 在所有 C++ 提交中击败了28.08%的用户

递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};

结果

执行用时 : 12 ms, 在所有 C++ 提交中击败了85.51%的用户
内存消耗 : 9.1 MB, 在所有 C++ 提交中击败了47.27%的用户

这个递归法有点意思，看了很久才赚过弯来。
在读代码+一步步画图解析之后，终于明白了其中的原理。
一行一行的讲解吧：

if (head == NULL || head->next == NULL) return head;

第一行是每个递归都需要的开始返回的条件。
第一个条件head == NULL 是处理[]这样的链表的特殊条件，并且在第二个条件head->next == NULL之前进行运算是为了防止在[]这样的空链表中运行head->next导致内存访问错误。
第二个条件是正常的递归跳出。搭配第2句、第5句就可以将尾节点不断的往上层调用栈返回。

ListNode* p = reverseList(head->next);

使用一个临时指针将第一句返回的尾节点存起来，以便最后返回。

head->next->next = head;
head->next = NULL;

这两句要一起看，我们先来看看每一次递归调用栈运行的时候链表的情况吧，以链表[1,2,3,4,null]为例。n在那个节点下面就代表那个节点的next指向null，h代表head指向，p代表临时指针p指向（最后返回的p也是这个）。

初始状态：

1->2->3->4
         n

第3层调用栈

      h  p
1->2->3<-4
      n

第2层调用栈

   h     p
1->2<-3<-4
   n

第1层调用栈

h        p
1<-2<-3<-4
n

可以看出在head指向的那个节点处运算过后就会将后一个节点的next指向本节点，以此往复就会将整条链表都换向。
而将本节点的next指向null我觉得是加强算法完整性来做的，因为是一个函数自己递归，所以要保证最后返回的链表最后一个节点要指向null，所以需要这一步。
可以看出p指针永远都是指向尾节点，并且一层一层的往上返回，感觉这一点设计很巧妙就是了。