目录
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);
*/时间： 击败了23.27%
内存： 击败了97.38%
