wordpress建中文网站,制作复杂的企业网站首页,国外 网站设计,贵州省建设厅建筑官方网站每日一题(LeetCode)----链表–两两交换链表中的节点
1.题目#xff08;[24. 两两交换链表中的节点](https://leetcode.cn/problems/spiral-matrix/)#xff09; 给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内…每日一题(LeetCode)----链表–两两交换链表中的节点
1.题目[24. 两两交换链表中的节点](https://leetcode.cn/problems/spiral-matrix/) 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。 示例 1 输入head [1,2,3,4] 输出[2,1,4,3] 示例 2 输入head [] 输出[] 示例 3 输入head [1] 输出[1] 提示 链表中节点的数目在范围 [0, 100] 内 0 Node.val 100
2.解题思路
思路一
先拆分成两个链表之后再进行合并
1.拆分
我们遍历一遍原链表通过下标的奇偶拆分成两个链表
2.合并
(1)我们以通过下标为奇数得到的链表的表头作为新链表的表头然后用两个指针变量交叉遍历两个链表交叉遍历就是一个链表向后遍历了一个节点之后就换另一个链表向后遍历一个节点这样循环直到两个链表都遍历完成结束
(2)将遍历到的节点放到新链表中即可(这里说是放到新链表中实际上只是改变了两个链表中的指针指向)
(3)最后我们返回这个新链表的表头
注意如果给出的链表没有节点或者只有一个节点我们不需要进行操作直接返回原有链表即可
思路二迭代法
1.我们创建一个虚拟头节点方便我们进行迭代操作如下图 2.遍历链表实现两两交换
如果当前操作节点的下一个和当前操作节点的下一个的下一个的下一个同时不为空进行下面操作
先保存一下当前操作节点的下一个节点和下一个的下一个节点为临时节点一和临时节点二
第一步当前操作节点的下一个指向操作开始的节点的下一个的下一个 第二步当前操作节点的下一个的下一个指向临时节点一 第三步当前操作节点的下一个的下一个的下一个指向临时节点二 第四步下一次操作节点为当前操作节点的下一个的下一个继续进行操作
看下图进行理解 思路三递归法
递归的终止条件是链表中没有节点或者链表中只有一个节点此时无法进行交换。
如果链表中至少有两个节点则在两两交换链表中的节点之后原始链表的头节点变成新的链表的第二个节点原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后更新节点之间的指针关系即可完成整个链表的两两交换。
3.写出代码
思路一的代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {//如果链表中没有元素那么返回链表即可if(headnullptr||head-nextnullptr){return head;}//拆成两个链表ListNode* head1head;ListNode* head2head-next;ListNode* Temp1head1;ListNode* Temp2head2;//进行拆分int flag0;while(Temp1Temp2){if(flag%20){Temp1-nextTemp2-next;Temp1Temp1-next;flag;}else{Temp2-nextTemp1-next;Temp2Temp2-next;flag;}}Temp1head1;Temp2head2;flag0;while(Temp1Temp2){if(flag%20){ListNode* delay2Temp2-next;Temp2-nextTemp1;Temp2delay2;flag;}else{ListNode* delay1Temp1-next;Temp1-nextTemp2;Temp1delay1;flag;}}return head2;}
};思路二的代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyheadnew ListNode(0);dummyhead-nexthead;ListNode* curdummyhead;while(cur-next!nullptrcur-next-next!nullptr){ListNode* temp1cur-next;ListNode* temp2cur-next-next-next;cur-nextcur-next-next;cur-next-nexttemp1;cur-next-next-nexttemp2;curcur-next-next;}return dummyhead-next;}
};思路三的代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {if(headnullptr||head-nextnullptr){return head;}ListNode* newHeadhead-next;head-nextswapPairs(newHead-next);newHead-nexthead;return newHead;}
};
