网站建设公司推荐 金石下拉,万盛建设局官方网站,工作表现怎么写,wordpress禁止前台登录【题干】
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
【思路】
先说递归的#xff0c;退出条件很明显#xff0c;当剩…【题干】
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
【思路】
先说递归的退出条件很明显当剩余节点不足两个的时候退出递归条件可以写为tail-nexttail-next-next短路运算也保证了不会进行nullptr的next运算函数体内执行第一节点和第二节点的交换即可交换后的第二节点连接更内层递归返回的节点返回交换后的第一节点的指针用于和前面部分连接。再说说迭代法首先创造一个伪头部指向新的链表头节点防止其丢失然后就是常规的链表节点交换的操作要注意许多防止指针丢失的细节保留尾指针用于和后续剩余节点连接的细节等等具体就直接看代码吧最后还是不要忘了把伪头部申请的内存释放哦
【题解】
递归
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;}
};
迭代
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* temp dummyHead;while (temp-next ! nullptr temp-next-next ! nullptr) {ListNode* node1 temp-next;ListNode* node2 temp-next-next;temp-next node2;node1-next node2-next;node2-next node1;temp node1;}ListNode* ans dummyHead-next;delete dummyHead;return ans;}
};
