【校招VIP】算法考点之链表题型解析- 校招VIP

考点介绍：

单链表题型是校招算法考察中出现频度比较高的一种，中小公司一般从指针的交换方向考察；一二线公司从单双指针、复杂度、环的问题角度考察。

答案详情解析和文章内容可扫下方二维码或链接即可查看！

一、考点题目

1.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（）

A.s->next=p->next; p->next=s

B.s->next=p;q->next=s;

C.p->next=s->next; s->next=p

D.p->next=s; s->next=q

解答：正确答案是 B

q->next=s表示将q与p之间断链，q指向s，s->next=p表示将s指向p，把链连接起来

2. 有一个双向链表，结点有两个指针域，llink和rlink分别指向前趋及后继，链中结点数大于2，设p指向链表中的一个结点，且p不是第一个结点。现要求删去p所指结点，则正确的删除是

A.p->llink->rlink=p->llink; p->llink->rlink=p->rlink;dispose(p);

B.dispose(p);p->llink->r1ink=p->llink; p->llink->rlink=p->rlink;

C.p->llink->rlink=p->llink; dispose(p);p->llink->r1ink=p->rlink;

D.p->llink->rlink=p->rlink:;p->rlink->llink=p->llink;dispose(p);

解答：正确答案是 D

3.一个长度为n的单向链表，用O(1) 空间复杂度来实现倒转输出，使用最低时间复杂度

解答：空间复杂度为O(1)，只能一次取一个结点，并把它的next结点指向第一个结点，具体分析，可以从1个结点入手，再到2个结点，3个结点......

4.找出单链表的中间元素，要求用时最少

解答：正常的话，需要先遍历一圈，得到链表长度。再从头遍历到1/2长度的位置。也就是走了1.5倍的链表长度......

5.判断单链表中是否有环，写出代码

解答：如果只用一个指针next的话，是不能知道到底有环造成一直循环还是链表长度很长造成的，而且循环了的话，程序没有终结态......

（答案点击下方链接或者扫海报二维码查看哦）

二、考点文章

1.一步一步写算法（之单向链表）

有的时候，处于内存中的数据并不是连续的。那么这时候，我们就需要在数据结构中添加一个属性，这个属性会记录下面一个数据的地址......

2.【数据结构】链表的原理及java实现

链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。下面对单向链表做一个介绍......

（扫下方海报二维码查看完整版）