力扣-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.排序链表
题面:
基本分析:我是先把所有值存起来然后构建链表的暴力写法
代码：
/**
* 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; // 更新 value
return;
}
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的链表专题，下一篇是其他专题的习题，希望有所帮助，一同进步，共勉！
原文地址：https://blog.csdn.net/2301_79232523/article/details/143862304
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！