反转链表 (opens new window)

• 难度：Easy
• 标签：链表反转 递归 尾递归

刷题思路

• [x] 迭代法
• [x] 自递归法 -- 反转后尾接
• [x] 尾递归法
• [x] 特殊解法：reduce 构造链表

方法 1 迭代法

• 思路: 创建res存储"已完成反转的结果" & 推进指针curr，推进直到curr为空，返回res.
• 复杂度：
  • 时间 O(N): 一次遍历
  • 空间 O(1): 常数级额外空间故 O(1).
• Leetcode 结果:
  • 执行用时: 60 ms, 在所有 JavaScript 提交中击败了 99 %的用户
  • 内存消耗: 34.9 MB, 在所有 JavaScript 提交中击败 51 %的用户

var reverseList = function(head) {
    let [res, curr] = [null, head] // res存储结果, curr推进
    while (curr) {
        const next = curr.next  // 1. 临时存储当前节点后续内容
        curr.next = res         // 2. 反转链表，当前节点指向"已完成反转的结果"
        res = curr              // 3. 存储"最新完成反转的结果"
        curr = next             // 4. 接回临时存储的后续内容, 当前节点继续推进

        // 简化: 以上四行等价于下面一行
        // [curr.next, res, curr] = [res, curr, curr.next]
    }
    return res
};

方法 2 自递归法 -- 反转后尾接

• 思路: 自递归无法存储推进状态所以无法尾递归，不断将 next 放入递归方法反转链表，结果.next = 当前节点. （Tip: 记得推进结果直到 next.next 为空）
• 复杂度：
  • 时间 O(N): 每层时间复杂度均为 O(1), 总共 n-1 层递归，故时间复杂度为 O(n).
  • 空间 O(N): 递归调用栈消耗空间，共 n-1 层递归，故空间复杂度为 O(n).
• Leetcode 结果:
  • 执行用时: 68 ms, 在所有 JavaScript 提交中击败了 85 %的用户
  • 内存消耗: 35.2 MB, 在所有 JavaScript 提交中击败 24 %的用户

var reverseList = function(head) {
    // if (!head || !head.next) return head
    // const next = head.next // 当前节点的后续部分将被反转，next节点反转后成为"反转部分的尾节点"
    // const reverseHead = reverseList(next)
    // head.next = null // 通过剪裁使当前节点成为"末节点"
    // next.next = head // 把"末节点"尾接到"反转部分的尾节点"之后
    // return reverseHead

    // 简化如下：
    if (!head || !head.next) return head
    const reverseHead = reverseList(head.next) // 反转链表
    head.next.next = head // 把"末节点"尾接到"反转部分的尾节点"之后
    head.next = null // 通过剪裁使当前节点成为"末节点"
    return reverseHead
};

方法 3 尾递归法

• 思路: 用 res 和 curr 存储推进状态，直到 curr 为空则输出结果.

• 复杂度:

  • 时间: O(n): 等同于正常推进，故 O(n).
  • 空间: O(1): 尾递归方式，重复使用一个空间故空间复杂度为 O(1).

• 结果:

  • 执行用时: 60 ms, 在所有 JavaScript 提交中击败了 98 %的用户
  • 内存消耗: 35.2 MB, 在所有 JavaScript 提交中击败 27 %的用户

  var reverseList = function(head) {
      return reverse(null, head)
  };
  
  function reverse (res, curr) {
      if (!curr) return prev
      let tmp = curr.next
      curr.next = res
      return reverse(curr, tmp)
  }
  

方法 4 特殊解法：reduce 构造链表

• 思路: 转数组后 reduce 构造出链表
• 模仿自: 转换成对应的数字直接相加 (opens new window)
• 复杂度:
  • 时间: O(n): 两轮遍历.
  • 空间: O(1): 结果不算额外空间，但确实是非原地反转算法.
• 结果:
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了87.14%的用户
  • 内存消耗：39.2 MB, 在所有 JavaScript 提交中击败了15.43%的用户

var reverseList = function(head) {
    if (!head || !head.next) return head
    const arr = []
    while (head) {
        arr.push(head.val)
        head = head.next
    }
    return arr.reduce((acc, v) => { return { val: v, next: acc } }, null)
};

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~