建网站底部怎么做的,做网站空间百度云和阿里云区别,互联网技术的应用,网站内页设计反转链表递归求解 206. 反转链表解法①#xff1a;取下一个节点在当前头节点前插入解法②#xff1a;反转每个节点next的指向解法③#xff1a;递归 92.反转链表Ⅱ反转left到right间节点的next指向 234.回文链表解法①#xff1a;将链表元素存在数组中#xff0c;在数组上… 反转链表递归求解 206. 反转链表解法①取下一个节点在当前头节点前插入解法②反转每个节点next的指向解法③递归 92.反转链表Ⅱ反转left到right间节点的next指向 234.回文链表解法①将链表元素存在数组中在数组上判断回文解法②在链表上反转前半部分链表和后半部分对比解法③递归 206. 反转链表
题目链接206.反转链表 题目内容 理解题意没有特殊要求就是把链表反转相当于从之前的末尾指向开头。
解法①取下一个节点在当前头节点前插入
第一种方法最容易想到从前往后遍历链表的同时每次从原链表中取下当前节点插入到新链表的开头。 这里的新链表实际就是该节点之前所有节点已经反转后构成的链表过程如下 5
代码如下C
//依次取出每个节点并将其插入在新链表的头部
class Solution {
public:ListNode* reverseList(ListNode* head) {//如果链表为空直接返回空指针if(!head)return nullptr;ListNode *currNode head;//初始化新链表为空ListNode *newhead nullptr;while(currNode ! nullptr){ ListNode *tmp currNode-next;// currNode插入在新链表的头部currNode-next newhead; newhead currNode;//currNode移到下一个节点currNode tmp; }//返回新链表return newhead;}
}; 解法②反转每个节点next的指向
假设原链表中一前一后两个节点preNode和currNode指向是preNode-next currNode反转后链表中这俩节点的指向是currNode-next preNode。既然如此那么可以在遍历链表中节点的时候【当前节点就用currNode】直接改变其指针域 代码如下C
//遍历链表每个节点将next改变成指向前面
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* prev NULL; //prev前驱节点初始化为nullListNode* currNode head; //当前节点初始化为头节点while(currNode){ListNode* tmp currNode-next;//改变当前节点指针指向其前驱节点currNode-next prev;//prev和currNode都向后移动遍历链表节点prev currNode;currNode tmp;}return prev; //最后prev就是新的headcurrNode已经为null了}
};本质上解法①和解法②是一样的只是从两个角度去理解“反转”。
解法③递归
从前往后遍历链表节点并使用递归方法的时候要到最后一个节点才开始往前返回那么就是先反转后半截链表再向前返回到当前的节点再对当前节点处理。假设链表有k个节点
递归到第k个节点的时候递归终止并且这最后一个节点就是整个链表反转后的头节点直接返回该节点地址m1个节点作为后半截已经反转后的链表的尾节点其next指向null现在将m1和m个节点连接起来m1的next指向mm1个节点是后半截反转后的尾节点怎么找到m1个节点呢 【对于当前第m个节点其next依然指向m1个节点因此直接currNode-next-next currNode使m1个节点的next指向当前第m个节点】m现在作为m-1之后剩余链表反转后的尾节点其next应该指向null到第m个节点的时候m1~k个节点已经反转了并返回了新的头节点即便是加上第m个节点并反转第m个节点也是加在反转后链表的尾部因此上一步返回的新头节点是整个链表反转后头节点因此要一直向前返回这个地址
整个过程如图所示
代码如下C
class Solution{
public:ListNode* reverseList(ListNode* head) {//如果链表为空直接返回//如果已经遍历到最后一个节点最后一个节点就是反转后的头节点直接返回if(head nullptr || head-next nullptr)return head;//当前head之后的链表已经反转了并返回反转后的新头节点指针 ListNode *newhead reverseList(head-next);//将head-next的next指针指向当前head反转head-next-next head;//断开当前head和head-next之间原本的连接head-next nullptr;//返回的新头节点是整个链表反转后的头节点因此一直返回newheadreturn newhead;}
};92.反转链表Ⅱ
题目链接92.反转链表Ⅱ 题目内容 理解题意在对整个链表反转的基础上增加了限制条件——只反转给定的left~right位置间的节点。 完成left~right的反转后还需要让left之前的节点left_pre-next指向right还需要让left-next指向right-next。 以下解法为一遍访问链表完成left~right之间的节点的反转
反转left到right间节点的next指向
整个过程分为以下几步
需要记录的节点有left、right、left前面一个节点left_pre和right后面一个节点right-next先遍历链表找到left_pre和left从left开始到right用反转链表题目的解法反转这一段链表用到pre和currNode两个变量保存当前要改变指向的节点、以及之前的一个节点上一步循环结束时pre就是rightcurrNode就是right-next 此时建立新连接left_pre-next right【即pre】left-next right-next【即currNode】 得到完整链表
上述过程为一次遍历链表在遍历的过程中改变left~right间的指向。全部代码如下C
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {//如果left和right相等没有节点要反向if(left right) return head;//存left和left前面一个节点的地址ListNode *leftNode head, *left_prev NULL;//定位到leftNode并保存left_prefor(int i1; ileft leftNode; i ){left_prev leftNode;leftNode leftNode-next;} //left~right间反向时用到的变量 ListNode *prev, *currNode; //当前节点和当前节点的前一个节点 prev leftNode;currNode prev-next;while(currNode left right){ListNode* tmp currNode-next;//反转next指向currNode-next prev;//pre和currNode都向前移动遍历left~right间节点prev currNode;currNode tmp;left;} //循环结束后pre是right节点currNode是right-next节点//左边节点leftNode指向right-nextleftNode-next currNode;//判断leftnode是不是头节点if(left_prev ! NULL) //如果不是left前面一个节点指向right节点left_prev-next prev;else //如果是新的头节点就是right节点head prev; return head;}
};234.回文链表
题目链接203.回文链表 题目内容 理解题意实际就是判断是不是回文【回文数从前往后、从后往前是一样的比如0123210判断两个指针一个开头一个结尾逐个对比全相等就是回文】只是换成了在链表上判断。 但是由于链表只能向next一个方向遍历不像数组、string等可以用下标index去定位。因此有两种解法
遍历链表并且把链表各个节点的val按照顺序存在vector里面然后在vector上比较直接在链表上比较
直接在链表上进行比较又有两种方法
遍历链表的同时用上面的反转链表方法把前半部分链表反转反转后的前半部分链表和后半部分链表的节点逐个对比val值都一样即为回文递归求解因为递归到最后一个节点才递归终止能够知道当前的节点的val一开始的head还在开头就能实现首尾比较一旦不相等其他节点就不用比较了直接向前返回false如果相等后面的节点向前返回到前面一个节点进行操作前面节点需要向后移动
解法①将链表元素存在数组中在数组上判断回文
这个方法最好理解也没有什么难度先遍历链表取出各个节点的val按原顺序存在vector中在vector上实现回文判断需要额外的空间…… 代码如下C
class Solution {
public:bool isPalindrome(ListNode* head) {vectorint val; //数组用于存储链表节点的valListNode *currNode head;//遍历链表节点并保存各个节点的valwhile(currNode){val.emplace_back(currNode-val);currNode currNode-next;}//双指针判断数组是否是回文的for(int i 0, j val.size() - 1; i j ; i,j--){//一旦有节点不相等就不是回文if(val[i] ! val[j])return false;}return true;}};解法②在链表上反转前半部分链表和后半部分对比
这个方法是一次遍历链表遍历的过程中同时反转链表这个反转结束的地方是链表的中间点 从这个中间点开始用一个指针逐个向前访问前面一段链表的节点再用一个指针逐个向后访问后面一段链表的节点并比较节点的val判断是否是回文过程如下所示 这里有个问题就是如何找到链表的中间节点用一个slow指针一个fast指针初始slow和fast都为head【没有附加头结点时】每次slow向后移动一个slow slow-next但是fast向后移动两个fast fast-next-next。当fast-next null的时候【有偶数个节点】或fast-next-next null的时候【有奇数个节点】终止此时的slow就定位在中间节点。 代码实现C
class Solution {
public:bool isPalindrome(ListNode* head) {//如果只有一个节点直接返回trueif(head-next nullptr)return true;//用slow、fast来寻找链表的中间点prev是slow前面一个节点辅助完成反转操作 ListNode *slow head,*fast head, *prev NULL;//找到中间节点并同时反转前半段链表while(fast-next fast-next-next){ fast fast-next-next; ListNode* tmp slow-next;slow-next prev;prev slow;slow tmp; } //上述循环结束时slow是(n1)/2节点//比如5个节点slow在第3个节点6个节点slow在第3个节点//且此时slow指向是原始的指向ListNode *right_head, *left_head; //左右两段一段向前一段向后链表的头节点right_head slow-next; //右边头节点就是slow-next//偶数个节点slow需要反转连接if(fast-next){ slow-next prev;left_head slow;}//奇数个节点slow不需要反转连接else{ left_head prev; }//两段链表节点逐个对比valwhile(left_head!nullptr right_head!nullptr){if(left_head-val ! right_head-val)return false;left_head left_head-next;right_head right_head-next;}return true;}
};其中奇数个节点、偶数个节点需要分开讨论写代码的时候要区分开。
解法③递归
这里的递归求解参考的力扣官方题解。因为递归到最后一个节点才递归终止能够知道当前的节点的val一开始的frontNode还在开头就能实现首尾比较一旦不相等其他节点就不用比较了直接向前返回false如果相等后面的节点向前返回到前面一个节点进行操作前面节点需要向后移动 递归的时候需要一个指针递归到最后向前返回那么还需要一个外部指针递归返回后它向后移动。 代码实现C
class Solution {
public:ListNode* frontNode; //需要定义一个全局的变量bool recursivelyCheck(ListNode *currNode){if(currNode){//后面已经有节点和前面的不相等中间一截不用比较了直接向上返回falseif(!recursivelyCheck(currNode-next))return false;//对比当前元素与前面对应元素是否一样if(currNode-val ! frontNode-val)return false;//将前面元素向后面移动一个frontNode frontNode-next;}return true;}bool isPalindrome(ListNode* head) {frontNode head; return recursivelyCheck(head);}
};
