凡科免费做的网站,北京百度关键词优化,wordpress为什么运行缓慢,安阳市地图1.前言
前五题在这http://t.csdnimg.cn/UeggB
休息一天#xff0c;今天继续刷题#xff01;
2.OJ题目训练
1. 编写代码#xff0c;以给定值x为基准将链表分割成两部分#xff0c;所有小于x的结点排在大于或等于x的结点之前 。链表分割_牛客题霸_牛客网
思路
既然涉及…1.前言
前五题在这http://t.csdnimg.cn/UeggB
休息一天今天继续刷题
2.OJ题目训练
1. 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前 。链表分割_牛客题霸_牛客网
思路
既然涉及到链表分割并且原本的数据的顺序不能改变那我们就要用到两个新的链表来存放值一边存放小于x的右边按顺序存放大于x的最后再将两个链表连起来形成新的链表就可以完成此题。 整个链表红色底线为小于3的值大于为绿色底线 遍历整个表将小于x的值放入ghead中同时更新gtail的值。 再将大于等于x的值放入Lhead表中更新Ltail的值 最后再通过gtail(前表尾节点)和Lhead(后表头节点)相连。返回ghead既为合并的表。
注意要点
涉及到改变头节点的方法应该添加标兵节点这样若其中一个表为空也不会报错 比x小的值在比x大的值后面的情况那他就会指回L表造成回环假设第二个1本来是在4的后面所以4的next节点还是指向1 释放标兵节点
附源代码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include cstdlib
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode *ghead,*gtail,*Lhead,*Ltail;ghead gtail (struct ListNode *) malloc(sizeof(struct ListNode));Lhead Ltail (struct ListNode *) malloc(sizeof(struct ListNode));struct ListNode *cur pHead;while(cur){if(cur-valx){Ltail-next cur;cur cur-next;LtailLtail-next;}else {gtail-next cur;cur cur-next;gtailgtail-next; }}Ltail-next ghead-next;struct ListNode * a Lhead-next;gtail-next NULL; //防止比x大的最后一个值下一个节点指向其他的值比x小的值在他后面的情况那他就会指回L表造成回环free(Lhead);free(ghead);return a;}
};
2. 链表的回文结构。
首先科普一下回文 可以形象的理解为正态分布就为回文反之不是。
方法
由于回文的基本特性我们可以将回文分成一半一半的两部分然后进行比较 分成红底进行比较但是由于链表的特殊性我们不能倒着比较。
所以就要对另一半进行逆序来比较 逆序后进行比较。
这样我们就可以用到我们之前题目的积累正所谓功夫不负有心人CV大法启动
附上链接 2. 反转一个单链表。 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 3. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 注意要点
中间节点要记录好因为后续比较要用到该如何判断比较的继续条件任何一个为NULL就结束
附源代码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head) {struct ListNode* tail head;while(tail-next){headhead-next;tailtail-next;if(tail-nextNULL){//headhead-next;}elsetailtail-next;}return head;}struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* curhead;struct ListNode* newhead NULL;while(cur){struct ListNode* nextcur-next;cur-next newhead; //指向新节点newhead cur;cur next;} return newhead;
}bool chkPalindrome(ListNode* A) {struct ListNode* mid middleNode(A);struct ListNode* rev reverseList(mid);while(Arev){if(A-val!rev-val){return false;}AA-next;revrev-next;}return true;
}
};3. 输入两个链表找出它们的第一个公共结点。
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
方法 大家要注意相交的链表的意思是后面的节点会交汇而不是交叉相交 根据这种链表的特点我们可以清楚他们的尾节点一定是相等的 通过这点我们就可以对是否为此类的链表进行判断。
再者我们发现如果是两个链表按照“顺序”第一个相等的就是相交节点 那么我们要怎么让两个节点的比较值相对整个表是一样的因为有长短不一的表 如果从首节点开始相互比较那他们永远都不会相等所以我们要做到同步比较 通过计算两表的长度让较长的表提前向前走差值步再进行比较当第一次比较相等时那就是相交节点
注意要点
在遍历尾节点时可以顺便计算链表长度对于长表的定义我们可以用指针替代然后再用各自对应的长度比较再进行长表指针的定义这样就可以节省掉很多if else语句。
附源代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curAheadA;struct ListNode *curBheadB;int lenA1,lenB1; //链表的长度至少为1while(curA-next) //计算链表A的长度及尾节点{lenA; //顺便计算表长curAcurA-next;}while(curB-next){lenB;curBcurB-next;}if(curA!curB){return NULL; //两边的为节点不相同那根本不是相交链表}int gapabs(lenA-lenB); //abs为取绝对值struct ListNode *longlistheadA; //假设A为长节点这里我们利用替身来表示长表struct ListNode *shortlistheadB; //就可以节省很多判断语句if(lenBlenA) //若B长侧替换{longlistheadB;shortlistheadA;}while(gap--){longlistlonglist-next; //先走差值步}while(longlist!shortlist) //不等于则同时向前遍历直到相等{longlistlonglist-next;shortlistshortlist-next;}return longlist; //返回第一个相等值
}
