面试经典150题——链表（二）

---

1、删除链表的倒数第 N 个结点

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

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

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

1.3 解题代码

/*** 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();dummyHead.next = head;ListNode cur = dummyHead;int num = 0;while(cur.next != null){num++;cur = cur.next;}int deleteNum = num - n + 1; // 倒数第 n 个就是 整数第 num - n + 1个 cur = dummyHead;for(int i = 0; i < deleteNum - 1; ++i){cur = cur.next;}cur.next = cur.next.next;return dummyHead.next;}
}

1.4 解题思路

1. 首先获取链表的总结点数num。
2. 那么删除的结点就是正数第num - n + 1个结点。
3. 按照链表的删除方式删除即可。

2、删除排序链表中的重复元素 II

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

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

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

2.3 解题代码

/*** 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) {ListNode dummyHead = new ListNode();dummyHead.next = head;ListNode cur = dummyHead;while(cur.next != null){ListNode nextNode = cur.next;int flag = 0;while(nextNode.next != null && nextNode.next.val == nextNode.val){flag = 1;nextNode = nextNode.next;}if(flag == 0){cur = cur.next;} else{cur.next = nextNode.next;}}return dummyHead.next;}
}

2.4 解题思路

1. 分情况讨论，cur指针指向判断结点的前1个结点，如果下一个结点存在相同的数字，则跳过这些数字，将cur.next与这些数字后面的一个数字所在的结点连接。否则的话，则需要保留这个结点，cur = cur.next。
2. 当cur.next为空的时候不需要判断下个数字了，跳出循环即可。

3、旋转链表

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

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

提示：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10⁹

3.3 解题代码

/*** 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(head == null){return head;}ListNode dummyHead = new ListNode();dummyHead.next = head;ListNode cur = dummyHead;int n = 0; // 链表中结点的个数while(cur.next != null){n++;cur = cur.next;}ListNode tail = cur;int step = k % n;if(step == 0){return head;}cur = dummyHead;for(int i = 0; i < n - step; ++i){cur = cur.next;}ListNode newHead = cur.next;tail.next = head;cur.next = null;return newHead;}
}

3.4 解题思路

1. 解题思路看上去是统一右移动k位，实际上是将链表在第n - k位和 n - k + 1截断然后重新拼接。
2. 第一段链表放在第二段链表的尾部即可。

4、分隔链表

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

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

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

4.3 解题代码

/*** 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 dummyHead1 = new ListNode(); // 存储所有小于x的结点ListNode dummyHead2 = new ListNode(); // 存储所有大于等于x的结点 ListNode cur1 = dummyHead1;ListNode cur2 = dummyHead2;ListNode cur = head;while(cur != null){if(cur.val < x){cur1.next = cur;cur1 = cur1.next;cur = cur.next;cur1.next = null;} else{cur2.next = cur;cur2 = cur2.next;cur = cur.next;cur2.next = null;}}cur1.next = dummyHead2.next;cur2.next = null;return dummyHead1.next;}
}

4.4 解题思路

1. 用两个链表进行维护即可，一个链表用来存储值小于x的所有的结点，另一个链表存储大于等于x的所有的结点。
2. 最后将两个链表拼接即可。

5、LRU 缓存

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

请你设计并实现一个满足 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) 的平均时间复杂度运行。

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 10⁵ 次 get 和 put

5.3 解题代码

public class DListNode{int key;int val;DListNode prev;DListNode next;DListNode(){}DListNode(int key, int val){this.key = key; this.val = val;}DListNode(int key, int val, DListNode prev, DListNode next){this.key = key;this.val = val;this.prev = prev;this.next = next;}
} class LRUCache {Map<Integer, DListNode> hash = new HashMap<Integer, DListNode>(); int size;int capacity;DListNode dummyHead = new DListNode();DListNode dummyTail = new DListNode();public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;dummyHead.next = dummyTail;dummyTail.prev = dummyHead;}public int get(int key) {if(hash.containsKey(key)){hash.get(key).prev.next = hash.get(key).next;hash.get(key).next.prev = hash.get(key).prev;moveToHead(hash.get(key));return hash.get(key).val; }return -1;}public void put(int key, int value) {DListNode node = new DListNode(key, value);if(hash.containsKey(key)){hash.get(key).val = value;hash.get(key).prev.next = hash.get(key).next;hash.get(key).next.prev = hash.get(key).prev;moveToHead(hash.get(key));} else{if(size < capacity){++size;moveToHead(node);} else{moveToHead(node);deleteTail();}hash.put(key, node);}}public void moveToHead(DListNode node){node.next = dummyHead.next;dummyHead.next = node;node.prev = dummyHead;node.next.prev = node;}public void deleteTail(){int key = dummyTail.prev.key;hash.remove(key);dummyTail.prev = dummyTail.prev.prev;dummyTail.prev.next = dummyTail;}
}/*** 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);*/

5.4 解题思路

1. 使用双向链表解决问题。
2. 对使用过的/新的值插入到链表开头。
3. 删除链表末尾的结点。