leetcode24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
题目分析
本题是关于链表中的节点两两交换的问题。给定一个链表，要求每两个节点一组进行翻转。例如，给定链表 1->2->3->4，翻转后变为 2->1->4->3。
算法选择
这个问题可以通过递归的方式来解决。递归的基本思想是将大问题分解为小问题，直到问题足够小可以直接解决。在这个问题中，我们可以将链表两两分组，然后递归地翻转每一组。
算法步骤
- 检查链表是否为空或只有一个节点，如果是，则直接返回链表。
- 创建一个新的头节点，指向原链表的第二个节点。
- 将原头节点与剩余链表（去除前两个节点）的翻转结果连接。
- 将新头节点的下一个节点设置为原头节点。
- 返回新头节点作为翻转后的链表的头。
算法流程
算法代码
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;}
};算法分析
- 时间复杂度：O(n)，其中n是链表的节点数。因为每个节点只被访问和修改一次。
- 空间复杂度：O(n)，由于递归使用栈空间，其空间复杂度为O(n)。
- 易错点：在连接节点时，要注意保持链表的连续性，避免出现断链或循环引用。
- 注意事项：递归的终止条件要正确设置，以避免无限递归。
相似题目
| 题目 | 题目链接 |
|---|---|
| 24. 两两交换链表中的节点 | 点击访问 |
| 25. K 个一组翻转链表 | 点击访问 |
| 61. 旋转链表 | 点击访问 |
