反转链表的五种方法

双指针法（迭代）

让前一个指针比后一个指针多走一步，然后让后一个的下一个保存下来，改变指针方向，然后让两个指针向后走便可。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *pre = NULL;
struct ListNode *cur = head;
while (cur) {
struct ListNode *temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}

递归法

在递的过程先将头节点一直往后给，直到下一个节点为空，此时将最后一个节点当作了新链表的头节点，然后开始归，先将此时的节点的下一个保存住，然后让下一个节点的下一个是这个节点，也就是此时的head，最后返回新的头节点便可。

注意\\,：在归的过程，需要在改变完节点方向时，需要将head的下一个方成空，否则成环，超出时间限制。

虚拟头节点

逻辑上，我将此法看作为迭代双指针，但是此处的虚拟头节点是本质存在的，而且是不变的，变的是dummy->next，此处可以省略头节点为NULL的情况

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode *cur = head;
while (cur) {
struct ListNode *nex = cur->next;
cur->next = dummy->next;
dummy->next = cur;
cur = nex;
}
return dummy->next;
}

数组—容器

这个可能是最笨重的方法，就是重新开辟个数组，先遍历存下链表的数组，然后再开一个链表来获取信息。这里要注意对开辟的链表进行初始化，否则会有不确定的值出现。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
int arr[5000];
int n = 0;
struct ListNode* cur = head;

while (cur) {
arr[n] = cur->val;
cur = cur->next;
n++;
}
struct ListNode* dummy = (struct ListNode* )malloc(sizeof(struct ListNode));
dummy->next = NULL;
struct ListNode* temp = dummy;
while (n—) {
struct ListNode* new = (struct ListNode* )malloc(sizeof(struct ListNode));
new->val = arr[n];
new->next = NULL;
temp->next = new;
temp = new;
}
return dummy->next;
}

尾递归

主要还是采用递归的思想，再设置一个函数，同时采用双指针，用递归替代赋值的思想。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* tool(struct ListNode* pre, struct ListNode* cur) {
if (cur == NULL) {
return pre;
}
struct ListNode* nex = cur->next;
cur->next = pre;
return tool(cur, nex);
}
struct ListNode* reverseList(struct ListNode* head) {
return tool(NULL, head);
}