题目
给你单链表的头节点 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的指向改为指向前一个节点，则相当于逆置*/
function reverseList2(head: ListNode | null): ListNode | null {
// 创建pre指针，指向当前节点的前一个节点，
let pre = null;
//当前节点的指针
let cur = head;
while (cur) {
//保存下一个节点，因为当修改了next指向前一个节点时，就无法找到下一个节点了
let nex = cur.next;
//将节点的next的指向改为指向前一个节点
cur.next = pre;
//向后移动两个指针
pre = cur;
cur = nex;
}
// cur这时候为null，pre为最后一个节点，也就是逆置后的头节点
return pre;
}
/** 递归 */
function reverseList(head: ListNode | null): ListNode | null {
//如果head 为空（只在链表为空时，!head 条件才会成立）
// !head.next 为空，则head为尾节点，则返回head
if (!head || !head.next) return head;
//递归链表，直到最后，并保存每一个节点
const newHead = reverseList(head.next);
//head 节点为当前节点，将下一个节点的next指针指回上一个节点
// 如 原本是 4 -> 5 -> 6 ，head为5 ，5.next = 6
// 此操作后为 4 -> 5 -> <- 6 ， 将 6.next = 5
head.next.next = head;
//由于上步操作后，5 和 6 相互指向，会成死循环，
// 此操作后 4 -> 5 <- 6
head.next = null;
// 由于递归为栈操作，所以最后返回的newHead为反转链表的表头
return newHead;
}
