扫码关注公众号

前端算法考察之链表算法
08-05
560观看
01

已知 pPre 为指向链表中某结点的指针, pNew 是指向新结点的指针,以下哪段伪码算法是将一个新结点插入到链表中 pPre 所指向结点的后面?

正确答案是C首先将旧结点的指针域(即pPre->Link,它存放着接下来的那个结点的地址)赋值给新结点的指针域(pNew->Link).这一步是因为:为了完成插入,新结点应该指向旧结点原来指向的元素。然后将指向新结点的指针(pNew,即新结点的地址)赋值给旧结点的指针域(pPre->Link),以让旧结点指向新结点。

来自:链表算法-链表算法
02

把链表分隔成 k 部分,每部分的长度都应该尽可能相同,排在前面的长度应该大于等于后面的

思路:首先遍历链表得到有效数字的个数,再求出分成k份的余数和每一份的均长,前面的部分长度加1直到余数为零。这样是为了保证长度尽可能相同的同时排在前面的长度大于后面的,例如将长度为5的链表分成三份,余2,每一份长度为1,将余下的加到前面,即[[1+1],[1+1],[1]]。classSolution{publicListNode[]splitListToParts(ListNoderoot,intk){intlen=0;ListNodecur=root;//遍历得出链表的有效数字while(cur!=null){cur=cur.next;len++;}//求出余数intmod=len%k;//等分的长度intsize=len/k;ListNode[]res=newListNode[k];cur=root;for(inti=0;i<k&&cur!=null;i++){res[i]=cur;intcursize=size+(mod-->0?1:0);for(intj=0;j<cursize-1;j++){cur=cur.next;}ListNodenext=cur.next;cur.next=null;cur=next;}returnres;}}

来自:链表算法-链表算法
03

求单链表中有效节点的个数(如果有头结点,不统计头结点)

publicstaticintgetLenth(Nodehead){if(head.next==null){return0;}intlenth=0;//让辅助指针指向头结点的下一个,就没有统计头结点Nodetemp=head.next;while(temp!=null){temp=temp.next;lenth++;}returnlenth;}

来自:链表算法-链表算法
课程
专栏
算法-链表算法-链表算法
3专栏
1课程
3 试题