24. 两两交换链表中的节点

📝 题目描述

给定一个链表，要求两两交换其中相邻的节点，并返回交换后链表的头节点。要求不能修改节点的数值，只能通过调整节点的指针完成交换。

📌 示例

示例 1

输入：head = [1,2,3,4] 输出：[2,1,4,3] 解释：原链表中相邻节点（1和2、3和4）两两交换，指针调整后得到新链表。

示例 2

输入：head = [] 输出：[]

示例 3

输入：head = [1] 输出：[1] 解释：只有一个节点，无需交换。

🚀 最优解：递归法

🔍 思路解析

核心策略：将“交换整个链表”拆解为交换当前相邻节点 + 递归处理剩余链表，利用递归的回溯特性完成指针调整：

1. 终止条件：当前节点为空，或当前节点的下一个节点为空（无相邻节点可交换）；
2. 递归逻辑：
   • 记录当前节点的下一个节点（记为 start，即交换后的新头节点）；
   • 调整指针：让 start 指向当前节点（完成当前对的交换）；
   • 递归处理当前节点的下下个节点（即剩余链表），并将结果作为当前节点的 next；
3. 返回值：返回交换后的新头节点（即 start）。

---

✅ 完整代码（Java）

import java.util.Scanner;

public class Main {
    private static ListNode buildList(String line) {
        if (line == null) {
            return null;
        }
        line = line.trim();
        if (line.isEmpty()) {
            return null;
        }
        String[] values = line.split(" ");
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (String val : values) {
            if (val.isEmpty()) {
                continue;
            }
            tail.next = new ListNode(Integer.parseInt(val));
            tail = tail.next;
        }
        return dummy.next;
    }

    private static void printList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) {
                sb.append(" ");
            }
            head = head.next;
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.hasNextLine() ? scanner.nextLine() : "";
        ListNode head = buildList(line);

        Solution solution = new Solution();
        ListNode result = solution.swapPairs(head);
        printList(result);
        scanner.close();
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 终止条件：无节点或只剩一个节点，无需交换
        if (head == null || head.next == null) {
            return head;
        }
        // start是当前对的第二个节点（交换后的新头）
        ListNode start = head.next;
        // 递归处理剩余链表，结果作为head的next
        head.next = swapPairs(start.next);
        // 交换当前对的指针：start指向head
        start.next = head;
        // 返回新的头节点
        return start;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

---

🧠 通俗易懂解释

可以把链表想象成“一串珠子”，两两交换的过程类似先交换前两颗，再把剩下的珠子递归交换后接回来：

• 比如链表 1→2→3→4：
  1. 先交换前两颗（1和2），得到 2→1；
  2. 递归交换剩下的 3→4，得到 4→3；
  3. 把 1 的 next 指向 4，最终得到 2→1→4→3。

以示例1（head = [1,2,3,4]）为例：

1. 初始 head=1，start=2；
2. 递归处理 start.next=3，进入子问题：
   • 子问题中 head=3，start=4；
   • 递归处理 start.next=null，返回 null；
   • 3.next=null，4.next=3，子问题返回 4；
3. 原问题中 1.next=4，2.next=1；
4. 返回 2，最终链表为 2→1→4→3。

---

⏱ 时间复杂度

• (O(n))（n 为链表长度） 递归遍历了链表中的每个节点，每个节点仅处理一次。

---

💾 空间复杂度

• (O(n/2) = O(n)) 递归调用栈的深度为链表长度的一半（每交换两个节点递归一次），空间消耗与链表长度成正比。