链表常见面试题
2023-02-18 16:40:28 时间
链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。
function FindKthToTail(head, k) {
if (head == null) {
return false;
}
var currNode = head;
var arr = [];
while (currNode != null) {
arr.push(currNode);
currNode = currNode.next;
}
return arr[arr.length - k];
}
合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
function Merge(pHead1, pHead2) {
if (pHead1 == null) {
return pHead2;
} else if (pHead2 == null) {
return pHead1;
}
var result = {};
if (pHead1.val < pHead2.val) {
result = pHead1;
result.next = Merge(pHead1.next, pHead2);
} else {
result = pHead2;
result.next = Merge(pHead1, pHead2.next);
}
return result;
}
复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
/*function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}*/
function Clone(pHead) {
if (!pHead) {
return null;
}
var newHead = new RandomListNode(pHead.label);
newHead.random = pHead.random;
newHead.next = Clone(pHead.next);
return newHead;
}
两个链表的第一个公共结点
输入两个链表,找出它们的第一个公共结点。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
var p1=pHead1;
var p2=pHead2;
while(p1!=p2){
p1=p1==null?pHead2:p1.next;
p2=p2==null?pHead1:p2.next;
}
return p1;
}
链表中环的入口结点
一个链表中包含环,请找出该链表的环的入口结点。
function EntryNodeOfLoop(pHead)
{
// write code here
if(pHead == null){
return 1;
}
if(pHead.next == null){
return null;
}
var fast = pHead;
var slow = pHead;
while(slow != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow) break;
}
var p1 = slow;
var p2 = pHead;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
删除链表中重复的结点
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
function deleteDuplication(pHead) {
var newHead = new ListNode('head');
newHead.next = pHead;
var pHead = newHead;
var qHead = pHead.next;
while (qHead) {
while ((qHead.next != null) && (qHead.val == qHead.next.val)) {
qHead = qHead.next;
}
//没移动
if (pHead.next == qHead) {
pHead = qHead;
qHead = qHead.next;
}
//移动了
else {
qHead = qHead.next;
pHead.next = qHead;
}
}
return newHead.next;
}
相关文章
- [PHP] 算法-数组归并排序并计算逆序对的个数的PHP实现
- [PHP] 算法-原址排序数组使奇数位于偶数前面的PHP实现
- 从源码角度解析线程池中顶层接口和抽象类
- Apache HBase MTTR 优化实践:减少恢复时长
- 低代码:时代的选择
- AI+云原生,把卫星遥感虐的死去活来
- 基于昇腾CANN的卡通图像生成可在线体验啦!十分钟带你了解CANN应用开发全流程
- 什么是强化学习?
- 高可用架构演进之单元化
- AOC萌新探索:搭建和体验在线AOC环境
- 如何将知识引入机器学习模型提升泛化能力?
- 零代码以“王者荣耀”为例解析设计七原则
- 高并发中,那些不得不说的线程池与ThreadPoolExecutor类
- “互联网+”大赛之智慧校园 赛题攻略:你的智慧校园,WeLink帮你来建
- 云小课 | 网络知识一箩筐——NAT网关,让IP地址华丽变身,轻松实现内外网互通
- 跟我读论文丨ACL2021 NER 模块化交互网络用于命名实体识别
- 4种基于像素分割的文本检测算法
- U2Net基于ModelArts Notbook的仿真实验
- 七夕赶上服务器架构升级,女朋友的约会怎么办
- 在openEuler上做开发?这个大赛拿出30万寻找开源的yyds