1.题目简介
翻转一个单链表，示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL。
原题链接：206.反转链表.
2.解法思路
要反转一个链表，可以定义一个新的链表来实现反转，但是内存空间消耗更大。在原链表的基础上可以通过双指针的方法来改变next的方向。
3.代码实现（C语言版）
3.1.1 双指针法
struct ListNode* reverseList(struct ListNode* head) {
typedef struct ListNode ListNode;
ListNode* cur = head;
ListNode* pre = NULL;
while(cur != NULL){
ListNode* tmp = cur->next;;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
简单解释：
首先定义一个指针cur和一个指针pre，cur初始指向头结点head，pre为NULL用于作为反转后链表的尾部所指向的NULL标志位。两个指针不断右移，遍历完链表并改变next指向。
- 定义别名，简化代码
- cur初始指向head节点，循环条件为在cur遍历完最后一个节点前循环都将继续，直到cur遍历到最末尾指向的NULL。
- 定义一个tmp临时节点指向cur的下一个节点，用于cur的移位。
- 将cur的next指向pre节点，相当于头结点指向一个NULL变成尾节点。后续cur和pre右移。
- pre移位到刚刚的cur处，而cur移位到之前的tmp处，即cur没有反转前原本指向的下一个节点。
- 继续循环，将cur指向pre，直到整个链表翻转完成。
- 此时cur变为了NULL，pre变成了新的头结点，返回pre得到新链表。
3.1.2递归法
递归法和双指针法思路是一样的，二者的时间复杂度都为0（n），因为每个节点都被访问一次。实现过程更简洁，但是也更抽象，而且有栈溢出风险。
新手推荐先学双指针法。 逻辑清晰易于理解，符合过程编程的逐步推进逻辑。
typedef struct ListNode ListNode;
ListNode* reverse(ListNode* pre, ListNode* cur)
{
if(!cur)return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
};
struct ListNode* reverseList(struct ListNode* head){
return reverse(NULL, head);
}
简单解释：
- 同样先定义别名。
- 定义一个翻转操作函数reverse用于递归实现。 其参数为一个pre节点和一个cur节点。会在下一个函数初始化。
- 设置递归终止条件： 检查cur是否为空指针。如果是，说明已经处理完了所有节点，返回pre，此时pre就是反转后的新头节点。
- 翻转节点： 如果没有中止，定义一个临时节点tmp存放cur原本的下一个节点，并将cur的next指向pre。
- 递归调用： 处理下一个节点tmp，并将cur和tmp （注意顺序） 作为新的参数传入递归函数中。直到触发终止条件。
- 在题目给定函数中直接调用递归函数，并初始化参数pre为NULL，初始化cur为头结点head。
4. 总结
本题还可以使用栈结构通过出栈入栈来实现翻转，也可以从链表尾部开始反转，具体实现不一一展示。
在反转过程中，注意几个事项：
- 双指针法时注意指针更新的顺序，在修改 cur->next 指向 pre 之前必须先以tmp暂存cur->next，否则无法找到正确的cur->next，导致链表断裂或无限循环。
- 递归法要注意终止条件，当cur为NULL时，返回pre作为新的头节点，如果终止条件错误，递归无法正确终止，可能导致栈溢出。
- 注意边界处理，空链表时反转还是NULL，单节点链表反转后还是自身。
- 注意typedef定义别名问题。若 typedef 定义为指针类型，如
typedef struct ListNode* ListNode;
则参数应为
ListNode pre, ListNode cur
而非
ListNode* pre, ListNode* cur。