力扣-Hot100-链表其三【算法学习day.36】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

---

习题

1.随机链表的复制

题目链接:138. 随机链表的复制 - 力扣（LeetCode）

题面:

基本分析:主要难在random的处理上，我看题解的

代码:

/*
// 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 {public Node copyRandomList(Node head) {for(Node i = head;i!=null;i=i.next){Node flag = new Node(i.val);flag.next = i.next;i.next = flag;i=i.next;}for(Node i = head;i!=null;i=i.next){if(i.random!=null){i.next.random = i.random.next;}i = i.next;}Node root = new Node(-1);Node node = new Node(-1);root.next = node;for(Node i = head;i!=null;i=i.next){node.next = i.next;i.next = node.next.next;node = node.next;}return root.next.next;}
}

---

2.排序链表

题目链接:148. 排序链表 - 力扣（LeetCode）

题面:

基本分析:我是先把所有值存起来然后构建链表的暴力写法

代码：

/*** 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) {int[] arr = new int[50005];int count =  0;for(ListNode i = head;i!=null;i=i.next){arr[count++] = i.val;}Arrays.sort(arr,0,count);ListNode p = head;for(int i = 0;i<count;i++){p.val = arr[i];p = p.next;}return head;}
}

---

3.LRU缓存

题目链接:146. LRU 缓存 - 力扣（LeetCode）

题面:

基本分析:把整个过程想象成一叠书，可以看看灵神的题解

代码:

class LRUCache {private static class Node {int key, value;Node prev, next;Node(int k, int v) {key = k;value = v;}}private final int capacity;private final Node dummy = new Node(0, 0); // 哨兵节点private final Map<Integer, Node> keyToNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;dummy.prev = dummy;dummy.next = dummy;}public int get(int key) {Node node = getNode(key);return node != null ? node.value : -1;}public void put(int key, int value) {Node node = getNode(key);if (node != null) { // 有这本书node.value = value; // 更新 valuereturn;}node = new Node(key, value); // 新书keyToNode.put(key, node);pushFront(node); // 放在最上面if (keyToNode.size() > capacity) { // 书太多了Node backNode = dummy.prev;keyToNode.remove(backNode.key);remove(backNode); // 去掉最后一本书}}// 获取 key 对应的节点，同时把该节点移到链表头部private Node getNode(int key) {if (!keyToNode.containsKey(key)) { // 没有这本书return null;}Node node = keyToNode.get(key); // 有这本书remove(node); // 把这本书抽出来pushFront(node); // 放在最上面return node;}// 删除一个节点（抽出一本书）private void remove(Node x) {x.prev.next = x.next;x.next.prev = x.prev;}// 在链表头添加一个节点（把一本书放在最上面）private void pushFront(Node x) {x.prev = dummy;x.next = dummy.next;x.prev.next = x;x.next.prev = x;}
}

---

4.合并k个升序链表

题目链接:23. 合并 K 个升序链表 - 力扣（LeetCode）

题面:

基本分析:暴力做法还是很好做的，把所有值存数组，排序后构造一个数组并返回

代码:

/*** 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) {int[] arr = new int[10005];int count = 0;for(ListNode node : lists){for(ListNode i = node;i!=null;i=i.next){arr[count++] = i.val;}}Arrays.sort(arr,0,count);ListNode root = new ListNode(0);ListNode node = new ListNode(0);root.next = node;for(int i = 0;i<count;i++){ListNode flag = new ListNode(arr[i]);node.next = flag;node = node.next;}return root.next.next;}
}

---

后言

上面是力扣Hot100的链表专题，下一篇是其他专题的习题，希望有所帮助，一同进步，共勉！