【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的指向改为指向前一个节点，则相当于逆置*/
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为尾节点，则返回headif (!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 = 5head.next.next = head;//由于上步操作后，5 和 6 相互指向，会成死循环，// 此操作后  4 -> 5 <- 6head.next = null;// 由于递归为栈操作，所以最后返回的newHead为反转链表的表头return newHead;
}