C++递归解决两两交换链表中节点
📟作者主页：慢热的陕西人
🌴专栏链接：力扣刷题日记
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
题目描述
解题思路
这一题的思路和上一道题反转链表的思路十分类似：
首先我们编写递归终止的条件：
if(head == nullptr || head->next == nullptr) return head; //当我们遇到一个只有一个节点的指针我们不进行交换直接返回head即可，同样的空链表也是同样的情况
首先我们坚信
ListNode* swapPairs(ListNode* head)函数可以帮我们解决掉head->next->next及之后节点的交换问题：那么我们只需要交换前两个节点并返回
head->next即可
ListNode* ret = swapPairs(head->next->next); ListNode* hn = head->next; head->next->next = head; head->next = ret; return hn;
以上就是整道题的思路了
代码
lass Solution { public: ListNode* swapPairs(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* ret = swapPairs(head->next->next); ListNode* hn = head->next; head->next->next = head; head->next = ret; return hn; } };
复杂度分析
时间复杂度
相当于深度优先遍历链表：O(N);
空间复杂度
没有额外使用空间O(1);
