24. 两两交换链表中的节点
3 min
题目
解法：递归交换
思路
核心思想是递归交换相邻节点。每次递归处理一对节点，将原第二节点作为新头节点，递归处理剩余链表。
正确性在于：递归终止条件（空链表或单节点）直接返回；对于两个以上节点，交换当前两个节点后，剩余链表通过递归自动完成交换，且指针重连保持了链表结构完整。
- Step 1: 若链表为空或只有一个节点，直接返回头节点
- Step 2: 将第二节点设为新头节点（p）
- Step 3: 将原头节点的next指向递归处理剩余链表的结果（从第三节点开始）
- Step 4: 将新头节点的next指向原头节点完成交换
- Step 5: 返回新头节点
复杂度
- 时间复杂度: ，其中为链表长度。每个节点被访问一次，递归深度为。
- 空间复杂度: ，递归调用栈的深度，最坏情况下链表长度为时递归深度为。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(head == NULL || head->next == NULL)
{
return head;
}
ListNode* p = head->next;
head->next = swapPairs(p->next);
p->next = head;
return p;
}
};