企业官网建设流程全解析

递归解法详解

题目要求两两交换链表中的相邻节点，且不能修改节点的值，只能交换节点本身。递归方法通过分解问题为子问题来实现。

递归思路将链表的前两个节点视为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

1. 第一次递归：head=1，newHead=2，递归处理3。
2. 第二次递归：head=3，newHead=4，递归处理nullptr，返回nullptr。
3. 连接子链表结果：3->next=nullptr，4->next=3，返回4。
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; } };

执行流程

1. 初始化虚拟头节点dummy，prev指向dummy。
2. 循环中交换first和second节点，更新prev->next和first->next。
3. 移动prev到first，继续处理下一对节点。

复杂度分析

• 时间复杂度：$O(n)$，遍历链表一次。
• 空间复杂度：$O(1)$，仅使用常数空间。