济南美赞网站建设公司,装修设计网站哪个好用,中国发达国家还有多远,德阳网站建设公司哪家好文章目录 链表分割环形链表有效的括号 链表分割
链接: 链表分割 虽然这个题牛客网中只有C,但是无所谓#xff0c;我们只要知道C是兼容C的就可以了 至于说这个题的思路#xff0c;我们就弄两个链表#xff0c;把小于x的结点放到一个链表中#xff0c;剩下的放到另一个链表… 文章目录 链表分割环形链表有效的括号 链表分割
链接: 链表分割 虽然这个题牛客网中只有C,但是无所谓我们只要知道C是兼容C的就可以了 至于说这个题的思路我们就弄两个链表把小于x的结点放到一个链表中剩下的放到另一个链表中最后把两个链表串起来就可以了 实现方式的话有两种一种是链表带哨兵位一种是不带带哨兵位的话处理起来比较简单很多判断条件是不需要的不带的话就相对要麻烦一些但是你如果对链表的操作比较熟悉的话其实还行 下面是带哨兵位的实现
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *curpHead;struct ListNode *head1,*head2,*tail1,*tail2;//1的是小值2的是大值//开辟哨兵位head1tail1(struct ListNode *)malloc(sizeof(struct ListNode ));head2tail2(struct ListNode *)malloc(sizeof(struct ListNode ));
while(cur){struct ListNode *nextcur-next;if(cur-valx){tail1-nextcur;tail1tail1-next;tail1-nextNULL;}else{tail2-nextcur;tail2tail2-next;tail2-nextNULL;}curnext;
}
//把两个链表接到一起如果第一个链表为空也无所谓
tail1-nexthead2-next;struct ListNode *headhead1-next;free(head1);//没用的就free掉free(head2);
return head;}
};下面是不带哨兵位的实现
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *curpHead;struct ListNode *head1NULL,*head2NULL,*tail1NULL,*tail2NULL;//一般都是定义两组指针一组管理一个链表while(cur){struct ListNode *tmpcur;curcur-next;if(tmp-valx){
if(tail1NULL){//如果链表为空head1tail1tmp;tail1-nextNULL;
}
else{tail1-nexttmp;tail1tail1-next;tail1-nextNULL;
}}else{
if(tail2NULL){head2tail2tmp;tail2-nextNULL;
}
else{tail2-nexttmp;tail2tail2-next;tail2-nextNULL;
}}}//合并两个链表if(head1NULL){//判断第一个表是否为空return head2;}else{tail1-nexthead2;return head1;}}
};环形链表
链接环形链表 这个题的话需要一些数学推理去找它们之间的关系要不然不太好说 我们假如说起始位置到入环处的距离为a入环出到相遇处距离为b环的周长为c在之前我们已经能判断一个链表中是否有环了就是通过两个指针一个fast一回走两步一个slow一回走一步那么它们两个之间有一定的数学关系就是2*(ab)ancb,化简一下为c-bc(n-1)a,这是什么意思啊就是一个指针从头走一个指针从相遇处走以相同的速度最后就会在那个相遇入环点相遇 下面我们来实现一下
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fasthead,*slowhead;
while(fastfast-next){//能出循环就没有环有环在循环中返回
fastfast-next-next;
slowslow-next;if(fastslow){
struct ListNode *tmpfast;
while(tmp!head){//相同时停止并返回这个点
tmptmp-next;
headhead-next;
}
return head;}
}
return NULL;
}我们之前找过两个相交链表的相交位置这里我们如果把相遇点的前一个位置的next置为空就可以了需要注意前一个只能是fast的前一个 下面我们来实现一下
//找相交点的函数
//思路就是计算两个链表的长度长的先走差的长度数最后同时走相同了就找到了
struct ListNode *meetpoint(struct ListNode *s1,struct ListNode *s2){int num10;int num20;struct ListNode *head1s1,*head2s2;while(head1){num1;head1head1-next;}while(head2){num2;head2head2-next;}struct ListNode *thelongs1,*theshorts2;if(num2num1){thelongs2;theshorts1;}int numabs(num1-num2);//求差的长度数while(num){thelongthelong-next;num--;}while(thelong!theshort){thelongthelong-next;theshorttheshort-next;}return thelong;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fasthead,*slowhead;
while(fastfast-next){struct ListNode *fastprevfast-next;//记录一下fast的上个位置
fastfast-next-next;slowslow-next;if(fastslow){fastprev-nextNULL;return meetpoint(head,slow);}
}
return NULL;
}有效的括号
链接有效的括号 这个题是用栈来实现的正好利用了栈的特性左括号入栈右括号判断出栈如果不匹配就返回false bool isValid(char * s){ST st;STInit(st);
while(*s){if(*s(||*s[||*s{){//左括号入栈STPush(st,*s);}else{if(STEmpty(st)){//栈为空并且要处理的字符为右括号STDestroy(st);return false;}char tmpSTTop(st);//匹配栈顶元素和要处理的元素if(*s)tmp!(||*s]tmp