【LeetCode24】两两交换链表中的节点（递归）

【LeetCode24】两两交换链表中的节点（递归）

文章目录

​​一、题目​​​​二、思路​​​​三、代码​​

一、题目

二、思路

可以使用递归方法：

递归终止条件：链表中没有节点，或者只剩下一个节点（不能进行交换了）。递归体：首先用​​head​​​保存原始链表的头节点，​​newhead​​​保存新链表的头节点（即​​head->next​​​），则原始链表的其他节点开始是​​newhead->next​​​。解决递归需要清楚递推公式含义：这里递推公式​​swapPairs()​​​指将给定的链表中的相邻节点两两交换后返回，返回的是交换完成的链表的头节点。所以假设我们已经将​​head->next​​​后的节点都处理完了，并且返回头结点​​subResult​​（即第三个节点），那么剩下就要交换第一个节点和第二个节点，并保持不断链即可。

三、代码

/** * 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 == nullptr || head->next == nullptr){ return head; } //subResult是head->next后的头节点 ListNode* subResult = swapPairs(head->next->next); ListNode* headNext = head->next; headNext->next = head; head->next = subResult; return headNext; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。