两两交换链表中的节点 (opens new window)

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

刷题思路

• [x] 迭代法
• [x] 自递归法

方法 1 迭代法

• 思路: 迭代法.
  • 思路: 使用哨兵头节点， 推进指针prev从当前哨兵节点位置出发，故prev.next=head，确认接下来两个节点(prev.next, prev.next.next)是否为空
    • 若不为空则开始交换, 交换后curr推进一格, prev推进两格, 循环继续;
    • 若有一个或一个以上为空则直接返回哨兵head节点的next;
• 复杂度：
  • 时间 O(N) 一次遍历
  • 空间 O(1)
• 结果：
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了72.69%的用户
  • 内存消耗：37.2 MB, 在所有 JavaScript 提交中击败了21.95%的用户

var swapPairs = function(head) {
    // 1. head 链表长度大于等于 2
    if (!head || !head.next) return head
    const newHead = new ListNode(null)
    newHead.next = head
    let [prev, curr] = [newHead, newHead.next] // prev 从虚拟哨兵节点开始，curr 从第一个真实节点开始
    while (curr && curr.next) {
        // prev -> curr后一个， curr后一个 -> curr， curr -> prev
        [prev.next, curr.next.next, curr.next] = [curr.next, curr, curr.next.next]
        curr = curr.next // 交换后 curr 处于原来 curr.next 的位置上，故只需推进一格即可到达下一组第一节点
        prev = prev.next.next // 交换后 prev 位置不变，故需推进两格才能到达下一组的前面
    }
    return newHead.next
};

方法 2 自递归法

• 思路: 明确输入、终止条件、返回值、递归方法逻辑
  • 输入：自递归的输入恒为第一个节点;
  • 终止条件：剩余长度小于2;
  • 返回值：已经完成交换的后续链表;
  • 递归方法逻辑：同上面方法，res = 1.next && 1.next=已完成交换的后续链表 && res.next = 1
• 复杂度：
  • 时间 O(N). 从最底层两个互换到最高层，每层时间复杂度均为O(1), 共 N/2 层故时间复杂度为 O(N/2).
  • 空间 O(N). 递归调用栈等同于层级, 即 O(N/2).
• 结果：
  • 执行用时：92 ms, 在所有 JavaScript 提交中击败了20.98%的用户
  • 内存消耗：37.2 MB, 在所有 JavaScript 提交中击败了23.96%的用户

var swapPairs = function(head) {
    // 1. head 链表长度大于等于 2
    if (!head || !head.next) return head
    // 2. 拿第二节点
    let newHead = head.next
    // 3. 第一节点指向第三节点, 第三节点递归处理
    head.next = swapPairs(head.next.next)
    // 4. 原第二节点指向原第一节点
    newHead.next = head
    // 5. 返回原第二节点(翻转后为第一节点)
    return newHead
};

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