【Leetcode刷题随笔】206.反转链表

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。