两个一组翻转链表：递归与迭代实现方法详解

翻转链表是一个常见的算法问题，通常用于考察对链表操作的理解。对于“两个一组翻转链表”的问题，我们可以通过递归或迭代的方式来实现。下面我将详细解释这两种方法，并提供相应的代码示例。

问题描述

给定一个链表，要求每两个相邻的节点进行翻转，并返回翻转后的链表。如果链表中的节点数为奇数，则最后一个节点保持原样。

例如：

• 输入：1 -> 2 -> 3 -> 4 -> 5
• 输出：2 -> 1 -> 4 -> 3 -> 5

方法一：递归

递归是一种直观的解决方法。我们可以将链表分成两部分：前两个节点和剩余的链表。先翻转前两个节点，然后递归处理剩余的链表。

function swapPairs(head) {
    // 递归终止条件：链表为空或只有一个节点
    if (head === null || head.next === null) {
        return head;
    }

    // 保存第二个节点
    const nextNode = head.next;

    // 递归处理剩余的链表
    head.next = swapPairs(nextNode.next);

    // 翻转当前两个节点
    nextNode.next = head;

    // 返回新的头节点
    return nextNode;
}

方法二：迭代

迭代方法通过遍历链表，逐个翻转每两个节点。我们需要维护一个虚拟头节点（dummy node）来简化边界条件的处理。

function swapPairs(head) {
    // 创建一个虚拟头节点
    const dummy = new ListNode(0);
    dummy.next = head;

    let prev = dummy;

    while (head !== null && head.next !== null) {
        // 保存第二个节点
        const nextNode = head.next;

        // 翻转当前两个节点
        head.next = nextNode.next;
        nextNode.next = head;
        prev.next = nextNode;

        // 移动指针
        prev = head;
        head = head.next;
    }

    // 返回新的头节点
    return dummy.next;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。每个节点最多被访问两次。
• 空间复杂度：
  • 递归方法：O(n)，递归调用栈的深度为 n/2。
  • 迭代方法：O(1)，只使用了常数级别的额外空间。

总结

• 递归方法：代码简洁，易于理解，但空间复杂度较高。
• 迭代方法：空间复杂度较低，适合处理较长的链表。

根据实际需求和链表长度，可以选择合适的方法来实现两个一组翻转链表。