残缺高频题库仓库地址：https://github.com/hzfe/awesome-interview
残缺高频题库浏览地址：https://febook.hzfe.org/
题目形容
定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点。
示例：
输出: 1->2->3->4->5->NULL输入: 5->4->3->2->1->NULL解法一：迭代（双指针）
在线链接
本办法是对链表进行遍历，而后在拜访各节点时批改 next 的指向，达到反转链表的目标。
- 初始化 cur 和 pre 两个节点，别离指向 head 和 null。
- 对链表进行循环，申明 temp 节点用来保留以后节点的下一个节点。
- 批改以后节点 cur 的 next 指针指向为 pre 节点。
- pre 节点批改为 cur 节点。
- cur 节点批改为 temp 节点。
- 持续进行解决，直到 cur 节点为 null，返回 pre 节点。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */const reverseList = (head) => { let cur = head; // 正向链表的头指针 let pre = null; // 反向链表的头指针 while (cur) { const temp = cur.next; // 暂存以后节点的后续节点，用于更新正向链表 cur.next = pre; // 将以后节点指向反向链表，这是一个建设反向链接的过程 pre = cur; // 更新反向链表的头指针为以后已解决的节点，反向链表的该轮构建实现 cur = temp; // 将正向链表头指针替换为暂存的节点，正向链表解决实现，开始下一轮解决 } return pre;};复杂度剖析
- 工夫复杂度 O(N)：遍历链表应用线性大小工夫。
- 空间复杂度 O(1)：变量 pre 和 cur 应用常数大小额定空间。
解法二：递归
在线链接
当应用递归对链表进行解决时，从链表的第一个节点登程，而后找到最初一个节点，该节点就是反转链表的头结点，而后进行回溯解决。
- 初始链表的头结点，head 标识。
- 如果 head 为空或者 head.next 为空，返回 head。
- 定义 reverseHead 节点，保留反转的链表值。
- 每次让 head 下一个节点的 next 指向 head，造成反转。
- 递归解决到最初一个节点，返回 reverseHead。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */const reverseList = (head) => { // 判断以后节点是否还须要解决 if (head == null || head.next == null) { return head; } // 递归解决后续节点 const reverseHead = reverseList(head.next); // 部分反转节点 head.next.next = head; head.next = null; return reverseHead;};复杂度剖析：
- 工夫复杂度 O(N)：n 是链表的长度，须要对链表的每个节点进行反转操作。
- 空间复杂度 O(N)：n 是链表的长度，空间复杂度次要取决于递归调用的栈空间，最多为 n 层。
参考资料
- 剑指 offer