数据结构（二），Java开发工程师笔试题目

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)]

本文已被CODING开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码】收录