关于前端:前端最高频的算法题之一反转链表

残缺高频题库仓库地址：https://github.com/hzfe/awesome-interview

残缺高频题库浏览地址：https://febook.hzfe.org/

题目形容

定义一个函数，输出一个链表的头节点，反转该链表并输入反转后链表的头节点。

示例：

 输出: 1->2->3->4->5->NULL
输入: 5->4->3->2->1->NULL

解法一：迭代（双指针）

在线链接

本办法是对链表进行遍历，而后在拜访各节点时批改 next 的指向，达到反转链表的目标。

1. 初始化 cur 和 pre 两个节点，别离指向 head 和 null。
2. 对链表进行循环，申明 temp 节点用来保留以后节点的下一个节点。
3. 批改以后节点 cur 的 next 指针指向为 pre 节点。
4. pre 节点批改为 cur 节点。
5. cur 节点批改为 temp 节点。
6. 持续进行解决，直到 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 应用常数大小额定空间。

解法二：递归

在线链接

当应用递归对链表进行解决时，从链表的第一个节点登程，而后找到最初一个节点，该节点就是反转链表的头结点，而后进行回溯解决。

1. 初始链表的头结点，head 标识。
2. 如果 head 为空或者 head.next 为空，返回 head。
3. 定义 reverseHead 节点，保留反转的链表值。
4. 每次让 head 下一个节点的 next 指向 head，造成反转。
5. 递归解决到最初一个节点，返回 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 层。

参考资料

1. 剑指 offer