起源：力扣（LeetCode）
给你单链表的头节点 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
办法一：迭代
var reverseList = function(head) {
let cur = head;
let pre = null;
while (cur) {
let temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp
}
return pre;
};- 工夫复杂度：O(n)
- 空间复杂度：O(1)O(1)。
办法二：递归
如果要让节点 1 和节点 2 反转的话，能够这样做：
head.next.next = head;
head.next = null; // 1 <= 2咱们递归就是一直地利用这种思维：
reverseList: head=1
reverseList: head=2
reverseList: head=3
reverseList:head=4
reverseList:head=5
终止返回
cur = 5
4.next.next->4，即 5 ->4
cur = 5 -> 4 -> null
3.next.next->3，即 4 ->3
cur = 5 -> 4 -> 3 -> null
2.next.next->2，即 3 ->2
cur = 5 -> 4 -> 3 -> 2 -> null
1.next.next->1，即 2 ->1
cur = 5 -> 4 -> 3 -> 2 -> 1 -> null
请看代码：
var reverseList = function(head) {if (head == null || head.next == null) {return head;};
let newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};- 工夫复杂度：O(n)
- 空间复杂度：O(n)