两两交换链表中的节点
递归解法详解
题目要求两两交换链表中的相邻节点，且不能修改节点的值，只能交换节点本身。递归方法通过分解问题为子问题来实现。
递归思路将链表的前两个节点视为node1和node2，交换这两个节点后，node1的下一个节点应指向剩余链表交换后的头节点。递归终止条件是链表为空或只有一个节点。
代码实现（C++）
class Solution { public: ListNode* swapPairs(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = head->next; head->next = swapPairs(newHead->next); newHead->next = head; return newHead; } };执行流程示例输入链表：1 → 2 → 3 → 4
- 第一次递归：
head=1，newHead=2，递归处理3。 - 第二次递归：
head=3，newHead=4，递归处理nullptr，返回nullptr。 - 连接子链表结果：
3->next=nullptr，4->next=3，返回4。 - 最终连接：
1->next=4，2->next=1，返回2，结果为2→1→4→3。
复杂度分析
- 时间复杂度：$O(n)$，每个节点处理一次。
- 空间复杂度：$O(n)$，递归栈深度为$n/2$。
迭代解法补充
迭代思路使用指针遍历链表，每次交换相邻两个节点，并更新指针位置。
代码实现（C++）
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; while (prev->next && prev->next->next) { ListNode* first = prev->next; ListNode* second = first->next; prev->next = second; first->next = second->next; second->next = first; prev = first; } return dummy.next; } };执行流程
- 初始化虚拟头节点
dummy，prev指向dummy。 - 循环中交换
first和second节点，更新prev->next和first->next。 - 移动
prev到first，继续处理下一对节点。
复杂度分析
- 时间复杂度：$O(n)$，遍历链表一次。
- 空间复杂度：$O(1)$，仅使用常数空间。