住房和城乡建设部执业资格注册中心网站,网站工商网监标,北京随喜设计网站,企业邮箱登录入口免费leetcode 150道题 计划花两个月时候刷完#xff0c;今天#xff08;第二十二天#xff09;完成了4道(50-53)150#xff1a;
50.#xff08;141. 环形链表#xff09;题目描述#xff1a;
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个…leetcode 150道题 计划花两个月时候刷完今天第二十二天完成了4道(50-53)150
50.141. 环形链表题目描述
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。第一版这个是经典的题目快慢指针就可以如果有环他们肯定会相遇没环一定会到 null
public class Solution {public boolean hasCycle(ListNode head) {ListNode lowhead;ListNode fasthead;while(fast!nulllow!null){lowlow.next;if(fast.nextnull){return false;}fastfast.next.next;if(lowfast){return true;}}return false;}
}第二版我总感觉我对这个起始的指针处理不好就看了一下解题他是反着去判断了也可以学习一下
public class Solution {public boolean hasCycle(ListNode head) {if(headnull||head.nextnull){return false;}ListNode lowhead;ListNode fasthead.next;while(low!fast){if(fastnull||fast.nextnull){return false;}fastfast.next.next;lowlow.next;}return true;}
}51.2. 两数相加题目描述
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。
示例 2
输入l1 [0], l2 [0]
输出[0]
示例 3
输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]
输出[8,9,9,9,0,0,0,1]第一版这个题我第一反应以为他第一个指针是最大位数。。看了好久才读懂了题目。。但是这个题目处理的应该是一个模板就是 3个while 的模板。。一般就是处理长度不一样的情况下我感觉都是3个while。。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode resnew ListNode(0);ListNode resTempres;int add0;while(l1!nulll2!null){int numl1.vall2.valadd;addnum/10;num%10;resTemp.nextnew ListNode(num);resTempresTemp.next;l1l1.next;l2l2.next;}while(l1!null){int numl1.valadd;addnum/10;num%10;resTemp.nextnew ListNode(num);resTempresTemp.next;l1l1.next;}while(l2!null){int numl2.valadd;addnum/10;num%10;resTemp.nextnew ListNode(num);resTempresTemp.next;l2l2.next;}if(add!0){resTemp.nextnew ListNode(add);resTempresTemp.next;}return res.next;}
}52.(21. 合并两个有序链表题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]第一版这个也是我上面说的长度不一样要一起处理的 3个while模板只不过这个是链表你只需要指定了头后面也会跟着这个头所以这块就是 一个 while 两个 if
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode resnew ListNode(0);ListNode resTempres;while(list1!nulllist2!null){if(list1.vallist2.val){resTemp.nextnew ListNode(list1.val);list1list1.next;}else{resTemp.nextnew ListNode(list2.val);list2list2.next;}resTempresTemp.next;}if(list1!null){resTemp.nextlist1;}if(list2!null){resTemp.nextlist2;}return res.next;}
}53.(138. 随机链表的复制) 题目描述
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。
random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。第一版这个题比较长意思就是每个节点都要新建我第一次写了好久但是写出来还是一坨。。
class Solution {public Node copyRandomList(Node head) {Node resnew Node(0);Node resTempres;Node headTemphead;MapNode,Integer nodeMapnew HashMap();int index0;while(headTemp!null){resTemp.nextnew Node(headTemp.val);nodeMap.put(headTemp,index);headTempheadTemp.next;resTempresTemp.next;}MapInteger,Integer indexMapnew HashMap();for (Map.EntryNode, Integer entry : nodeMap.entrySet()) {if(entry.getKey().randomnull){indexMap.put(entry.getValue(),-1);}elseindexMap.put(entry.getValue(),nodeMap.get(entry.getKey().random));}// 复制 random 开始resTempres.next;Node tempres.next;index0;while(resTemp!null){tempres.next;if(indexMap.get(index)!-1){for(int i0;iindexMap.get(index);i){temptemp.next;}resTemp.randomtemp;}index;resTempresTemp.next;}return res.next;}
}第二版看了解题真的这个思想很好把每个节点单独出来一个一个来赋值他的 next和 random
class Solution {public Node copyRandomList(Node head) {if(headnull){return null;}MapNode, Node nodeMap new HashMapNode, Node();Node headTemphead;while(headTemp!null){nodeMap.put(headTemp,new Node(headTemp.val));headTempheadTemp.next;}headTemphead;while(headTemp!null){Node nodeNewnodeMap.get(headTemp);if(headTemp.next!null){nodeNew.nextnodeMap.get(headTemp.next);}if(headTemp.random!null){nodeNew.randomnodeMap.get(headTemp.random);}headTempheadTemp.next;}return nodeMap.get(head);}
}昨天又鸽了一天。。不知道为啥昨天啥都不想干。。昨天把yys也删了超鬼王真的肝不动了。。
加油第二十二天了早日跳槽
