⭐ 题目日期：

滴滴 - 2024/10/30

🌳 题目描述：

链表每两个元素反转。（要求用迭代和递归两种方法实现）

示例 1:
输入：1 -> 2 -> 3-> 4 -> 5 -> 6
输出：2 -> 1 -> 4 -> 3 -> 6 -> 5

示例 2:
输入：1 -> 2 -> 3
输出：2 -> 1 -> 3

🕵🏽 面试评估：

这道题在常规的单链表反转的基础上加了点变化。1. 每两个节点反转 2. 要求迭代和递归两种解法。总体难度适中。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

迭代法：

递归法：

💻代码：

迭代法：

Java

public ListNode reverseEveryTwoNodes(ListNode head) {
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    ListNode cur = dummyNode.next;
    
    while (cur != null && cur.next != null) {
        ListNode next = cur.next.next;
        pre.next = cur.next;
        pre.next.next = cur;
        cur.next = next;
        pre = cur;
        cur = next;
    }
    
    return dummyNode.next;
}

递归法：

Java

public ListNode reverseEveryTwoNodes(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode firstNode = head;
    ListNode secondNode = head.next;

    firstNode.next = reverseEveryTwoNodes(secondNode.next);
    secondNode.next = firstNode;
    return secondNode;
}

🚵🏻复杂度分析：

迭代：

时间复杂度: O(n), 将链表上的所有节点访问一遍，故时间复杂度为 O(n), n 为链表中节点的个数

空间复杂度: O(1), 仅常数个变量被用到

递归：

时间复杂度: O(n), 将链表上的所有节点访问一遍，故时间复杂度为 O(n), n 为链表中节点的个数

空间复杂度: O(n), 每一个递归层有两个节点，所以递归一共调用 n / 2 层，递归调用的空间复杂度为 O(n)