网站建设要学什么,什么网站可以做项目,中小企业建立网站最经济的方式,广陵区建设局网站24. 两两交换链表中的节点 24. 两两交换链表中的节点两两节点分组#xff0c;反转两个节点连接递归求解 24. 两两交换链表中的节点
题目链接#xff1a;24. 两两交换链表中的节点 题目内容#xff1a; 题目中强调不能修改节点内部值#xff0c;是因为如果不加这个限制的话… 24. 两两交换链表中的节点 24. 两两交换链表中的节点两两节点分组反转两个节点连接递归求解 24. 两两交换链表中的节点
题目链接24. 两两交换链表中的节点 题目内容 题目中强调不能修改节点内部值是因为如果不加这个限制的话直接将两个节点的值交换就好了不涉及到节点间连接的重新建立很容易实现。但是加了这个限制以后就只能改变节点间的连接了。
两两节点分组反转两个节点连接
其实这就是一道涉及到链表基本操作的题目题目的要求是将链表中的节点按照两个两个的分组【包括组内、和前一组、和后一组改变节点连接的操作】
1、组内的两个节点原来是前一个节点currNode指向后一个节点tmp 【tmp currNode-next 】现在变成tmp-next currNode2、组内的前一个节点currNode现在指向下一组节点的【两个节点】的前面一个即currNode-next tmp-next【注意这里的tmp-next是第1步还未进行前原始的currNode的下下一个节点3、前一组节点【两个节点】的后面一个节点preNode原来是指向currNode的现在应该指向tmp
之后currNode向后移动遍历所有这样的分组。整个过程如下所示
实现细节
对于第一组节点交换两个节点后头节点会改变【以preNode是不是null来判断】因为是两两分组从当前分组变到下一个分组按道理应该是currNode currNode-next-next但是由于上述第2步中currNode-next tmp-next所以currNode currNode-next就达到了向前移动两个节点的目的如果总共有偶数个节点那么两两分组交换刚好如果是奇数个节点最后一个节点不变。
代码实现如下C
class Solution {
public:ListNode* swapPairs(ListNode* head) {//如果链表为空 或只有一个节点 不需要交换if(head nullptr || head-next nullptr)return head;//preNode是前一组节点里面的后面一个//currNode是当前一组节点中前面一个ListNode *preNode NULL, *currNode head;//遍历完的条件while(currNode currNode-next){ListNode *tmp currNode-next; //先保存这个指针currNode-next tmp-next; //改变和下一组节点的连接tmp-next currNode; //改变组内节点的连接if(preNode){ preNode-next tmp; //改变前一组节点和当前组节点的连接} else{ //如果preNode是nullptr说明是第一组头节点会改变head tmp;} //向后移动到下一个分组preNode currNode;currNode currNode-next; }return head;}
};递归求解
由于链表的定义是递归的这道题依旧可以用递归的办法来解决。先搞清楚以下三个问题
递归的终止条件是什么当前节点要做什么操作向前返回的是什么
递归依然是到递归终止条件才开始向前返回结果。所以是链表后半部分的分组先完成了组内节点连接的改变再向前返回返回的是后半部分链表完成了两两交换节点后的头节点。递归终止条件是headnull || head-next null。在当前节点需要做什么呢
交换组内节点即head-next这个节点要指向head【head-next-next head】;和后面部分链表返回的头节点连接head-next 递归函数返回的头结点向上返回从当前节点开始的这段链表完成两两节点交换后的头节点。
代码实现如下C
class Solution {
public:ListNode* swapPairs(ListNode* head) {//递归终止条件if(head nullptr || head-next nullptr)return head;//要返回的新头节点ListNode *newhead head-next; //与后半段链表完成了两两节点交换后返回的头节点建立新连接head-next swapPairs(head-next-next);//组内节点改变连接newhead-next head;//返回新头节点return newhead; }
};
