🔗 两两交换链表中的节点

题目来源：24. 两两交换链表中的节点 – 力扣（LeetCode）

📌 题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。

要求：

• 不能修改节点内部的值（即：只能通过修改指针进行节点交换）。
• 链表节点数范围：[0, 100]
• 0 <= Node.val <= 100

✅ 示例解析

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
解释：交换第1↔2、第3↔4节点。

示例 2：

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

示例 3：

输入：head = [1]
输出：[1]
解释：只有一个节点，无法交换，原样返回。

⚠️ 提示

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

💡 解法：虚拟头节点 + 指针操作 —— O(n) 时间，O(1) 空间

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode p = dummy;

        while (p.next != null && p.next.next != null) {
            ListNode first = p.next;      
            ListNode second = p.next.next;  

            // 三步指针重连：交换 first 和 second
            first.next = second.next;
            second.next = first;
            p.next = second;

            // p 前进到下一对节点的前驱（即当前的 first）
            p = first;
        }

        return dummy.next;
    }
}

📊 复杂度分析

• 时间复杂度：O(n)
  • 每两个节点处理一次，总共遍历一次链表。
• 空间复杂度：O(1) ✅
  • 仅使用常数个指针变量，无递归、无额外数据结构。

🧩 解题思路

核心思想：虚拟头节点 + 每次交换一对节点，通过指针重连实现“节点交换”

1. 边界处理：
   • 链表为空或只有一个节点 → 直接返回原链表。
2. 初始化：
   • 创建虚拟头节点 dummy，指向 head。
   • 使用指针 p 作为“前驱指针”，始终指向待交换节点对的前一个节点。
3. 交换逻辑（关键三步）： 假设当前待交换节点为 first 和 second：p → first → second → X目标变为：p → second → first → X操作顺序（必须按顺序，避免断链）：交换逻辑（关键三步）： 假设当前待交换节点为 first 和 second：p → first → second → X目标变为：p → second → first → X操作顺序（必须按顺序，避免断链）：
   • first.next = second.next → 先让 first 指向 second 的下一个（X）
   • second.next = first → 再让 second 指向 first
   • p.next = second → 最后让 p 指向 second（完成拼接）
4. 指针前进：
   • p = first（因为 first 现在是这一对的第二个节点，也是下一对的前驱）
5. 循环条件：
   • p.next != null && p.next.next != null
   • 确保至少还有两个节点可交换。
6. 返回：
   • dummy.next 为新链表头节点。

举例说明：

输入：head = [1,2,3,4]

初始：dummy → 1 → 2 → 3 → 4
          p^

第1轮：
first = 1, second = 2
操作：
1.next = 2.next → 1→3
2.next = 1      → 2→1
p.next = 2      → dummy→2→1→3→4
p = 1

当前：dummy → 2 → 1 → 3 → 4
                  p^

第2轮：
first = 3, second = 4
操作：
3.next = 4.next → 3→null
4.next = 3      → 4→3
p.next = 4      → 1→4→3
p = 3

最终：dummy → 2 → 1 → 4 → 3 ✅
返回 dummy.next → [2,1,4,3]

边界处理：

• 空链表 → 直接返回 null
• 单节点 → 不进入循环，直接返回原节点
• 奇数个节点 → 最后一个节点不交换，自然保留（如 [1,2,3] → [2,1,3]）