小鸡玩算法-力扣HOT100-链表（下）

一.随机链表的复制问题概述给你一个长度为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作为传入参数。思路本问就是让你重新深拷贝一份链表关键点是随机指针可能指向同一个节点如果没有随机指针就可以简单下面这么写那因为有就需要判断是否已存在这里用到map旧节点和新节点映射map在外面是为了预防每次递归都创建新的map那新创的都是空的代码/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } } */ class Solution { MapNode,Node mapnew HashMap(); public Node copyRandomList(Node head) { if(headnull){ return null; } if(!map.containsKey(head)){ Node tempnew Node(head.val); map.put(head,temp); temp.nextcopyRandomList(head.next); temp.randomcopyRandomList(head.random); } return map.get(head); } }二.排序链表问题概述给你链表的头结点head请将其按升序排列并返回排序后的链表。思路归并排序递归一分为二将左右两边先排好序号然后进行合并合并的过程小的先上。主方法当中看似没有进行排序实则是在合并的时候排序了。注找中点时fast!nullfast.next!null当为奇数时最后的fastnull,当为偶数时为fast.nextnull代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode sortList(ListNode head) { if(headnull||head.nextnull){ return head; } ListNode midfindMid(head); ListNode rightHeadmid.next; mid.nextnull; ListNode leftsortList(head); ListNode rightsortList(rightHead); return merge(left,right); } private ListNode findMid(ListNode head){ ListNode slowhead; ListNode fasthead.next; while(fast!nullfast.next!null){ slowslow.next; fastfast.next.next; } return slow; } private ListNode merge(ListNode h1,ListNode h2){ ListNode dummynew ListNode(0); ListNode curdummy; while(h1!nullh2!null){ if(h1.valh2.val){ cur.nextnew ListNode(h1.val); h1h1.next; }else{ cur.nextnew ListNode(h2.val); h2h2.next; } curcur.next; } cur.next(h1!null) ? h1:h2; return dummy.next; } }三.合并K个升序链表问题概述给你一个链表数组每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中返回合并后的链表。思路把多个合并分解成许许多多的两个合并。代码/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length0||listsnull){ return null; } ListNode res null; for(ListNode list:lists){ resmerge(res,list); } return res; } private ListNode merge(ListNode h1,ListNode h2){ ListNode dummynew ListNode(0); ListNode curdummy; while(h1!nullh2!null){ if(h1.valh2.val){ cur.nextnew ListNode(h1.val); h1h1.next; }else{ cur.nextnew ListNode(h2.val); h2h2.next; } curcur.next; } cur.next(h1!null) ? h1:h2; return dummy.next; } }四.LRU缓存问题概述请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。函数get和put必须以O(1)的平均时间复杂度运行。思路头放新的用到相当于刷新了map相当于展品柜里面放一个个样品球。然后get,put操作都是拿展品柜里的球进行排队当然如果队里满了装不下了展品柜里的样品球也扔了。代码class LRUCache { class DLinkedNode{ int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode(){}; public DLinkedNode(int key,int value){ this.keykey; this.valuevalue; } } private MapInteger,DLinkedNode cachenew HashMap(); private int size; private int capacity; private DLinkedNode head,tail; public LRUCache(int capacity) { this.size0; this.capacitycapacity; this.headnew DLinkedNode(); this.tailnew DLinkedNode(); head.nexttail; tail.prevhead; } public int get(int key) { DLinkedNode nodecache.get(key); if(nodenull){ return -1; }else{ removeToHead(node); return node.value; } } public void put(int key, int value) { DLinkedNode nodecache.get(key); if(nodenull){ DLinkedNode newNodenew DLinkedNode(key,value); cache.put(key,newNode); addToHead(newNode); size; if(sizecapacity){ DLinkedNode tempremoveTail(); cache.remove(temp.key); size--; } }else{ node.valuevalue; removeToHead(node); } } private void addToHead(DLinkedNode node){ node.prevhead; node.nexthead.next; head.next.prevnode; head.nextnode; } private void removeList(DLinkedNode node){ node.prev.nextnode.next; node.next.prevnode.prev; } private void removeToHead(DLinkedNode node){ removeList(node); addToHead(node); } private DLinkedNode removeTail(){ DLinkedNode nodetail.prev; removeList(node); return node; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj new LRUCache(capacity); * int param_1 obj.get(key); * obj.put(key,value); */