赞
踩
public:
ListNode(int value) {
this->value = value;
this->next = NULL;
}
void add_node(ListNode* next_node) {
this->next = next_node;
}
void set_value(int value) {
this->value = value;
}
int get_value() {
return this->value;
}
ListNode* get_next() {
return this->next;
}
//创建结点
ListNode* creat(int data ){
ListNode*p=NULL;
p = new ListNode();
if(NULL == p){
cout<<“申请内存失败”<<endl;
exit(-1);
}
p->value=data;
p->next=NULL; //处理干净身后事
return p;
}
//新增节点 这里默认头已经有了
void add(ListNode* the_head,int data ) {
ListNode* pNode = the_head;
//后面再接上一个
while (pNode->next != NULL){ //遍历链表,找到最后一个节点
pNode = pNode->next;
}
pNode->next = new ListNode(data);
}
//删除节点
void del(ListNode* the_head, int index){ //删除第index个节点
ListNode* pFree = NULL; //用来删除
if(index < 1){
return;
}
if(1 == index){
pFree = the_head;
head = the_head->next;
free(pFree->pData); //先释放数据
free(pFree); //释放指针
return;
}
ListNode* pNode = the_head;
while (pNode->next != NULL && index>2){
pNode = pNode->next;
}
pFree = pNode->next; //再指向数据域就爆了
pNode->next=pNode->next->next; //这里要无缝衔接
free(pFree->pData); //先释放数据
free(pFree); //释放指针
}
//计算节点数
int Count(ListNode* the_head){
int count = 0;
ListNode*pNode = the_head;
while (pNode != NULL){
pNode = pNode->next;
count++;
}
return count;
}
//查找固定节点数据
ListNode* find(ListNode* the_head,int index){
ListNode* pNode=NULL;
pNode=the_head;
while(pNode != NULL && index){
pNode = pNode->next;
index–;
}
if(NULL == pNode){
cout<<“节点不存在”<<endl; //可以写日志里
}
return pNode;
}
};
//判断链表成环
bool is_ring(ListNode* a) {
ListNode* fast = a,*slow = a;
while (fast->get_next()) {
fast = fast->get_next();
if (fast->get_next() && slow->get_next() && fast != slow) {
fast = fast->get_next();
slow = slow->get_next();
}
if (fast == slow) {
return true;
}
}
return false;
}
//寻找入环点(默认成环)
int find_ring(ListNode* a) {
ListNode* fast = a->get_next()->get_next(), * slow = a->get_next();
while (fast != slow) {
fast = fast->get_next()->get_next();
slow = slow->get_next();
}
ListNode* slow2 = a;
while (fast != slow2) {
fast = fast->get_next()->get_next();
slow2 = slow2->get_next();
}
return slow2->get_value();
}
//原地翻转链表
ListNode* reverse_list(ListNode* a) {
ListNode* temp = new ListNode(0);
ListNode* h = NULL;
while(a->get_next()) {
temp = a;
a = a->get_next();
temp->add_node(h);
h = temp;
}
return temp;
}
若将链表的左端固定,链表不断向右延伸,这种建立链表的方法称为尾插法。尾插法建立链表时,头指针固定不动,故必须设立一个搜索指针,向链表右边延伸,则整个算法中应设立三个链表指针,即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是头结点。
上面那个就是。
这个就比较需要脑子了,前边那个有手就行的。
我这个人,懒了点,来张现成的图吧。
看啊,在相遇之前呢,慢指针走的距离很好求的:L1 = D+S1;
快指针走的距离:设它在相遇前绕了n圈(n>1),那么:L2 = D+S1+n(S1+S2);
不过,还有一个等量关系,不要忽略掉,快指针的速度是慢指针的两倍,所以:L2 = 2L1;
那么就是:n(S1+S2)-S1 = D;
再转换一下就是:(n-1)(S1+S2)+S2 = D;
那也就是说,在相遇时候,把一个慢指针放在链表头,开始遍历,把一个慢指针放在相遇点开始转圈,当它俩相遇的时候,就是入环点了。
其实吧,用脑子想一开始很难想出来,用手想就快多了。
环的大小就不用我多说了吧,相遇之后,定住快指针,慢指针再绕一圈,再相遇的时候就是一圈了。
参考单链表。
小编13年上海交大毕业,曾经在小公司待过,也去过华为、OPPO等大厂,18年进入阿里一直到现在。
深知大多数初中级Java工程师,想要提升技能,往往是自己摸索成长,但自己不成体系的自学效果低效又漫长,而且极易碰到天花板技术停滞不前!
因此收集整理了一份《2024年最新Java开发全套学习资料》送给大家,初衷也很简单,就是希望能够帮助到想自学提升又不知道该从何学起的朋友,同时减轻大家的负担。
由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频
如果你觉得这些内容对你有帮助,可以添加下面V无偿领取!(备注Java)
由于篇幅过长,就不展示所有面试题了,感兴趣的小伙伴
更多笔记分享
JTBAvx-1711111864883)]
[外链图片转存中…(img-BXmo8nNK-1711111864884)]
由于文件比较大,这里只是将部分目录截图出来,每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频
如果你觉得这些内容对你有帮助,可以添加下面V无偿领取!(备注Java)
[外链图片转存中…(img-dUp7kvac-1711111864884)]
由于篇幅过长,就不展示所有面试题了,感兴趣的小伙伴
[外链图片转存中…(img-g9nSBKM2-1711111864885)]
[外链图片转存中…(img-HdRzPvXI-1711111864885)]
[外链图片转存中…(img-IauIRuT8-1711111864886)]
更多笔记分享
[外链图片转存中…(img-OGYXGO9Z-1711111864886)]
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。