【LeetCode-面试经典150题-day14】

19.删除链表的倒数第N个结点

82.删除排序链表中的重复元素Ⅱ

61. 旋转链表

86.分隔链表

146.LRU缓存

19.删除链表的倒数第N个结点

题意：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

【输入样例】head = [1,2,3,4,5],n=2

【输出样例】[1,2,3,5]

解题思路：

1. 双指针p和q，初始哈指向头节点；

2. 移动q，直到p和q之间相隔的元素为n

3. 同时移动p和q，直到q指向链表结尾的null

4. p.next = p.next.next

/*** 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 removeNthFromEnd(ListNode head, int n) {ListNode dummyHead = new ListNode(0,head);ListNode p = dummyHead;ListNode q = head;for(int i=0; i< n; i++){q = q.next;}while(q != null){q = q.next;p = p.next;}p.next = p.next.next;ListNode ans = dummyHead.next;return ans;}
}

时间：击败了100.00%

内存：击败了64.22%

82.删除排序链表中的重复元素Ⅱ

题意：

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

【输入样例】head = [1,1,1,2,3]

【输出样例】[2,3]

解题思路：

1. 定义一个哑节点，指向链表的头节点

2. 指针cur指向哑节点，遍历链表

3. 如果cur.next.val == cur.next.next.val,将cur.next以及后面拥有相同元素x(x=cur.next.val)的节点全部删除；

4. 不断移除重复元素，直到cur.next是空节点或元素值不等于x

/*** 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 deleteDuplicates(ListNode head) {if(head == null){return head;}ListNode dummy = new ListNode(0,head);ListNode cur = dummy;while(cur.next != null && cur.next.next != null){if(cur.next.val == cur.next.next.val){int x = cur.next.val;while(cur.next != null && cur.next.val == x){cur.next = cur.next.next;//不断跳过重复值的数}}else{cur = cur.next;//继续往下遍历}}return dummy.next;//指向head}
}

时间：击败了100.00%

内存：击败了86.54%

61. 旋转链表

题意：

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

【输入样例】head = [1,2,3,4,5],k=2

【输出样例】[4,5,1,2,3]

解题思路：

1. 定义一个哑节点，指向链表的头节点

2. 遍历链表，统计链表的长度，优化移动次数为k%n;

3. 将原始链表形成闭环，并计算count = n-k%n,表示从当前节点开始遍历count次，可以找到尾节点；

4. 不断移动指针，直到count = 0，此时定义一个新节点，指向dummy.next，作为新链表的头节点，dummy.next赋值null实现断链

/*** 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 rotateRight(ListNode head, int k) {if(k == 0 || head==null || head.next == null){return head;}//一次遍历，统计链表的长度n，移动k次相当于移动k%n次；int n = 1;ListNode dummy = head;while(dummy.next !=null){dummy = dummy.next;++n;}int count = n - k % n;if(count == n){return head;}dummy.next = head;//形成闭环while(count-- > 0){dummy = dummy.next;}ListNode result = dummy.next;dummy.next = null;return result;}
}

时间：击败了100.00%

内存：击败了68.97%

86.分隔链表

题意：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

【输入样例】head = [1,4,3,2,5,2],x=3

【输出样例】[1,2,2,4,3,5]

解题思路：

1.借助两个链表，一个存储小于x的节点，一个存储大于等于x的节点，之后将两个链表进行拼接即可。

/*** 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 partition(ListNode head, int x) {ListNode minNext = new ListNode(0);ListNode minhead = minNext;ListNode maxNext = new ListNode(0);ListNode maxhead = maxNext;while(head!=null){if(head.val < x){minNext.next = head;minNext = minNext.next;}else{maxNext.next = head;maxNext = maxNext.next;}head = head.next;}maxNext.next = null;minNext.next = maxhead.next;return minhead.next;}
}

时间：击败了100.00%

内存：击败了20.49%

146.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) 的平均时间复杂度运行。

【输入样例】

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

【输出样例】

[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

解题思路：哈希表+双向链表

1. 双向链表按照被使用的顺序存储键值对，最靠近头部的键值对是最近使用的，最靠近尾部的键值对是最久未使用的。

2. 哈希表缓存数据的键，映射到其在双向链表中的位置

3. 使用哈希表进行定位，找出缓存项在双向链表中的位置，并将其移动到双向链表的头部，如果key不存着哈希表中，则返回-1或者在链表的头部新建一个节点。

public class LRUCache {private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();private int size;private int capacity;private DLinkedNode head,tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if(node == null){//链表中不存在此值return -1;}//存在，将其移动到双向链表的头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node == null){//如果key不存着，要创建一个新节点//需要判断插入之后长度是否会超过容量DLinkedNode newNode = new DLinkedNode(key,value);cache.put(key,newNode);addToHead(newNode);++size;//每加进来一个元素，size++if(size > capacity){//删除尾部节点和哈希表中的对应项DLinkedNode tail = removeTail();cache.remove(tail.key);--size;}}else{//key存在，哈希表定位，修改value，移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node){//添加到双向链表头部node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node){//从当前位置移走node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode node = tail.prev;removeNode(node);return node;}
}class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key, int value){this.key = key;this.value = value;}
}
/*** 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);*/