目录
LeetCode之路——206. 反转链表
分析：
解法一：迭代
解法二：递归
LeetCode之路——206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
-
链表中节点的数目范围是
[0, 5000] -
-5000 <= Node.val <= 5000
分析：
解法一：迭代
重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态，每次处理都会改变状态，直到到达最终状态。
从前往后遍历链表时，将当前节点的next指针改为指向前一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要找下一个节点，所以需要一个变量保存当前节点curr，处理完需要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next。
-
定义变量对应prev，curr，next。
-
将当前节点存入curr变量 curr=head.
-
将下个节点指针保存到next = curr.next.
-
变换指针 curr.next = prev;
-
开始下一次迭代 prev = curr; curr=next;
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while(curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}
-
时间复杂度：O(n)
-
空间复杂度：O(1)
解法二：递归
以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历，大的问题（链表反转）拆解为性质相同的小问题（两个元素反转）。
-
从节点1和2开始拆解两元素反转发现链表断了。
-
所以从末尾开始拆解。
-
单次反转默认为A和B节点，head.next.next = head;head.next = null;
-
递归的边界条件就是head == null || head.next == null。
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}
-
时间复杂度：O(n)
-
空间复杂度：O(n)
