扫码关注公众号
已知 pPre 为指向链表中某结点的指针, pNew 是指向新结点的指针,以下哪段伪码算法是将一个新结点插入到链表中 pPre 所指向结点的后面?
正确答案是C首先将旧结点的指针域(即pPre->Link,它存放着接下来的那个结点的地址)赋值给新结点的指针域(pNew->Link).这一步是因为:为了完成插入,新结点应该指向旧结点原来指向的元素。然后将指向新结点的指针(pNew,即新结点的地址)赋值给旧结点的指针域(pPre->Link),以让旧结点指向新结点。
把链表分隔成 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;}}
求单链表中有效节点的个数(如果有头结点,不统计头结点)
publicstaticintgetLenth(Nodehead){if(head.next==null){return0;}intlenth=0;//让辅助指针指向头结点的下一个,就没有统计头结点Nodetemp=head.next;while(temp!=null){temp=temp.next;lenth++;}returnlenth;}
单向链表已经可以实现非连续存储,为什么还需要双向链表?()
正确答案是B将N条长度均为M的有序链表进行合并,合并后的链表也保持有序。为了解决这个问题,我们可以采用分治法和优先队列(如最小堆)。首先,我们可以将N条有序链表两两合并。合并两个长度为M的有序链表的时间复杂度是O(M)。因此,对于N条链表,合并它们的时间复杂度为O(N*M)。但是,我们需要进行logN轮合并,因为每次合并都将链表数量减半。所以,总的时间复杂度为O(N*M*logN)。另一种方法是使用优先队列(如最小堆)。我们可以将所有链表的头结点放入优先队列中,并按照它们的值进行排序。每次我们从优先队列中取出最小的元素,将其添加到结果链表中,并将其后继节点放入优先队列中。这个过程将持续到优先队列为空。在这种方法中,优先队列的大小为N,每次插入和删除操作的时间复杂度为O(logN)。我们需要进行N*M次插入和删除操作,因为合并后的链表有N*M个元素。因此,这种方法的时间复杂度也是O(N*M*logN)。