力扣hot100二刷——链表

第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”本身把握常用的函数。
标记把握程度表明办法⭐Fully 完全把握看到标题就有思绪，编程也很流利⭐⭐Basically 根本把握须要稍作思考，大概看到提示方法后能解答⭐⭐⭐Slightly 轻微把握须要看之前写过的代码才气想起怎么做多做⭐⭐⭐⭐absolutely no 完全没有把握须要看题解才知道怎么做背⭐⭐⭐⭐⭐有难度的高频题须要看题解才知道怎么做，而且过几天就忘了这道题怎么做了背背22⭐⭐Easy链表160/相交链表哈希表法，时间复杂度始终是O(M+N)    双指针法，时间复杂度最差是O(M+N)，指针A遍历完链表A再接着遍历链表B；指针B遍历完链表A再遍历链表A，两者走了雷同隔断时，即为答案（相交节点大概空节点）23⭐Easy链表206/反转链表界说三个指针：lastNode curNode nextNode，curNode  重新节点开始遍历直到curtNode == null时竣事遍历ListNode lastNode = null;24⭐⭐⭐Easy链表234/回文链表错误的思绪：先翻转链表，再比力翻转前后的链表，如许做翻转前的链表已经不存在了，没法比力  精确思绪：快慢指针先找到链表的中点，然后反转后半段链表，再比力链表的前半段和后半段25⭐Easy链表141/环形链表易错点：起主要清除输入为null的环境：if(head  == null) return null;  快慢指针遍历链表，假如两指针雷同则存在环形26⭐⭐Medium链表142/环形链表II在141题的根本上，多加一部即可     快慢指针相遇，证明有环   快指针指向头节点，慢指针稳固，两指针同时向后移动，直至相遇即为环节点27⭐⭐⭐Easy链表21/归并两个有序链表思绪很简单，但步伐有细节要留意     界说两个指针，分别指向两个链表的头节点   当两个指针所指节点均不为空时，比力它们的巨细，谁小就加在新链表后，而且后移该指针   跳出循环后，大概两条链表的节点都被参加新链表了，也有大概有一条链表另有节点没被参加新链表，以是要手动判断并参加。28⭐Medium链表2/两数相加要留意，判断末了的进位是否 > 0，> 0的话，链表末了再加上这个进位     对应位相加（要判断，节点是否为空，为空的话相当于加 0）   求出当前节点的值：（进位 + 节点1的值 + 节点2的值）% 10    更新进位：（进位 + 节点1的值 + 节点2的值）/ 10     记得后移指针29⭐⭐⭐Medium链表19/删除链表的倒数第N个节点界说快慢指针，快指针比慢指针快n个节点。      要留意的是，假如快指针到达队尾，阐明要删的恰恰是头节点，那么直接返回第二个节点       快慢指针向后移，直到快指针到达止境（下个节点为空），此时要删的就是慢指针的下个节点30⭐⭐⭐Medium链表24/两两互换链表中的节点哨兵节点+遍历链表的同时互换相邻节点     创建一个哨兵节点，并维护pre、cur、next三个节点   当pre.nextnull&&pre.next.nextnull       时，遍历链表，并互换节点。    步伐开始先清除head  == null || head.next == null的环境31⭐⭐⭐⭐Hard链表25/K个一组反转链表把链表分为三部分：已经反转的、要反转的、未反转的     找到此次要反转的部分的尾节点end，并把尾节点的下个节点置空；end.next == null ,竣事遍历   反转此部分链表（重点）   将该部分链表加到已经反转部分的反面32⭐⭐⭐Medium链表138/随机链表的复制利用哈希表来生存节点     遍历链表，将节点生存到哈希表Map<Node, Node>   再次遍历链表，将原节点中的next、random拷贝到新节点中33⭐⭐⭐⭐Medium链表148/排序链表归并排序     快慢指针将链表分为两半，一半为left，一半为right，假如head == null || head.next == null阐明不可以再分了，就竣事递归   left链表和right链表举行比力排序并归并，算法如21题。   末了要将不为空的节点参加到链表末了，再返转头节点。34⭐⭐⭐Hard链表23/归并k个升序链表升序的优先级队列 PriorityQueue     遍历数组，将每个链表的头节点参加到队列中   当队列不为空时，循环实行以下操纵    2.1 移除队头节点（最末节点）  2.2 将该节点的下一个节点参加到队列（假如不为null的话）35⭐⭐⭐⭐⭐Medium链表146/LRU缓存双向链表+哈希表  哈希表生存<key,  Node>，便于查找key  创建双向链表类与dummy哨兵节点     LRUCache(int capacity)    初始化容量、dummy节点的pre和next     get操纵    getKey()函数查找key是否存在，存在则返回value，否则返回-1；     put操纵    getKey()函数查找key是否存在，存在则更改原来的value为新的value；否则putFront()函数将key参加到最前面，而且要判断是否超出容量，超出的话要remove()删除尾节点     getkey()    查找哈希表中是否存在key，存在则putFront()函数将该节点参加到最前面，并返回Node，否则返回null     putFront()    将节点参加到最前面，也就是dummy的反面     remove()    删除尾节点，也就是dummy的前面PriorityQueue pq = new PriorityQueue<>((a,b) ->  a.val - b.val);图片版：