力扣Hot100-链表篇
大约 4 分钟
链表类题目说到底其实就是修改结点的next与pre指针指向，说起来蛮简单的，但实操起来一不注意很容易就会出问题。
其中，快慢指针法可以帮助解决一系列链表类问题。
而在力扣 Hot100 上关于链表的题目数量挺多的，所以仅对一些比较令人头疼的问题进行总结。（依然是忽略 hard 难度题目）
160.相交链表
对于这道题，自己有想出两种不同的方式来解决：
- 利用 Set 集合，先将一个链表储存在其中，再遍历另一个链表，用于判断是否相交。
- 双重循环暴力解决。
这两种方式都无法满足题目，空间复杂度 O(1)，时间复杂度 O(n) 的要求，一种方法满足了空间复杂度，一种方法满足了时间复杂度，但不能兼之。
看了题解给出的最优解，我只能说，妙啊！
public class Solution {
/**
* 核心思想就是消除两个链表的长度差
* 如何消除长度差？
* 1.对于短链表，走到终点后，再走一遍长链表
* 2.对于长链表，走到终点后，再走一遍短链表
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode nodeA = headA, nodeB = headB;
while (nodeA != nodeB) {
nodeA = nodeA == null ? headB : nodeA.next;
nodeB = nodeB == null ? headA : nodeB.next;
}
return nodeA;
}
}
234.回文链表🔥
花了一个小时想出来的 O(1) 空间复杂度最优解。
本以为官方题解有更优雅的解法，看了之后感觉大差不差，代码量还更大一些。
本质上就是先反转链表，然后再进行比较。
class Solution {
public boolean isPalindrome(ListNode head) {
if (head.next == null) return true;
ListNode nodeA = head;
int size = 0;
// 1.先求出链表长度
while (nodeA != null) {
size++;
nodeA = nodeA.next;
}
// 2.遍历到中间靠右的那个结点
int count = (size + 1) / 2;
ListNode nodeB = head;
for (int i = 0; i < count; i++) {
nodeB = nodeB.next;
}
// 3.反转左边链表
// 这里一定得注意分情况判断，防止在链表结点数为奇数的情况下，nodeA走到中间结点
if (size % 2 == 0) {
nodeA = head;
ListNode p = nodeA.next;
head.next = null;
while (p != nodeB) {
ListNode temp = p.next;
p.next = nodeA;
nodeA = p;
p = temp;
}
} else {
nodeA = head;
ListNode p = nodeA.next;
head.next = null;
while (p.next != nodeB) {
ListNode temp = p.next;
p.next = nodeA;
nodeA = p;
p = temp;
}
}
// 4.进行判断
while (nodeB != null) {
if (nodeA.val != nodeB.val) return false;
nodeA = nodeA.next;
nodeB = nodeB.next;
}
return true;
}
}
142.环形链表 Ⅱ
依然是使用快慢指针做，但涉及到了数学推导，和相交链表那题有异曲同工之妙。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null) {
if (fast.next == null || fast.next.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 快慢指针第一次相遇后，让快指针回到起点
fast = head;
// 快慢指针同速移动，下一次相遇时即是环的入口
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
24.两两交换链表中的结点
这道题有一点绕，不理清楚关系的话很容易就被绕进去了。
表明上来看是两个链表结点互相交换，实际上每次涉及到三个链表结点。
class Solution {
public ListNode swapPairs(ListNode head) {
// 在头结点前再建立一个虚拟结点
ListNode pre = new ListNode(0, head);
ListNode temp = pre;
while (temp.next != null && temp.next.next != null) {
ListNode start = temp.next, end = temp.next.next;
temp.next = end;
start.next = end.next;
end.next =start;
temp = start;
}
return pre.next;
}
}
146.LRU 缓存
思路还是比较简单的，就是代码量不小。
使用哈希表建立 key 与 value 的映射关系，通过双向链表来记录 key 最近是否有使用。
怎么写这道题比较好呢？
- 先把双向链表定义好；
- 再定义一系列成员变量；
- 写 put 与 get 方法；
- 最后完善双向链表有关的操作。
class LRUCache {
// 1.定义双向链表
private class DListNode {
private int key;
private int val;
private DListNode pre;
private DListNode next;
public DListNode() {}
public DListNode(int key, int val) {
this.val = val;
this.key = key;
}
}
// 2.定义一系列变量
private int size;
private int capacity;
// 指向头结点，头部储存最近使用的
private DListNode head;
// 指向尾结点，尾部储存最近未使用的
private DListNode tail;
private Map<Integer, DListNode> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
size = 0;
head = new DListNode();
tail = new DListNode();
head.next = tail;
tail.pre = head;
cache = new HashMap<>();
}
// 3.写put与get方法
public int get(int key) {
if (cache.containsKey(key)) {
DListNode node = cache.get(key);
// 移动至链表头部
moveToHead(node);
return node.val;
}
return -1;
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
DListNode node = cache.get(key);
node.val = value;
moveToHead(node);
return;
}
size++;
DListNode node = new DListNode(key, value);
cache.put(key, node);
// 添加至链表头部
addToHead(node);
if (size > capacity) {
// 移除尾结点
node = removeTail();
cache.remove(node.key);
size--;
}
}
// 4.完善双向链表相关的方法
private void addToHead(DListNode node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
private void removeNode(DListNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void moveToHead(DListNode node) {
removeNode(node);
addToHead(node);
}
private DListNode removeTail() {
DListNode node = tail.pre;
removeNode(node);
return node;
}
}