最近集中刷了一批链表的题型，在这里总结一下解题技巧，以及对应题目的解题思路。
解题思路并不会细致入微，主要是为了总结归类，并且希望用几句话来激发灵感，权当是没思路时的指引以及以后复习时的提纲了。
还有一些重要或者总会绕晕的经典题目，也在这里记录一下代码的实现逻辑。
遇到链表相关的题，无论问题是什么，先要想想是不是可以用上以下的两个技巧。
1、哨兵节点
哨兵节点是一个非常常用的链表技巧，在处理链表边界问题的场景下，可以减少我们代码的复杂度。主要解决的问题如下：
因为哨兵节点使用场景很广泛，所以在这里就不针对性的列出典型题目了。
2、双指针
双指针实在是太好用了，其实不止是链表，对于数组题来说，也是非常好用的技巧。
双指针的主要用法有以下几种：
有时，你需要将两条链表合并成一条链表，或者要将一条链表拆分成两条链表。此时，需要用两个指针分别在两条链表上行走，并处理逻辑。
典型题目：
- 21. 合并两个有序链表：两个指针在两条链表上行走，哪个指针指向的节点值大，则将该节点放到合并后的链表上，指针继续向前一步。
- 86. 分隔链表：根据指定的目标值，将一个链表先分割成两个链表。因此，需要两个指针在分割出来的两个链表上行走。之后再将两个链表直接头尾合并。
- 160. 相交链表：两个指针在两条链表上行走，当一个指针指向当前列表的结尾时，继续遍历另外一个链表。这样可以保证两个指针指向相同的节点时，这个节点就是相交节点。
快指针的速度是慢指针 n 倍，则当快指针走完时，慢指针停留的地方就是整个链表的 1/n 处（大概位置）。一般情况下都是慢指针走一步，快指针走两步。
典型题目：
- 876. 链表的中间结点：快指针走两步，慢指针走一步。快指针走到结尾时，则慢指针在中间位置。
- 141. 环形链表：快指针走两步，慢指针走一步。当快慢指针相遇时，从头结点再出发一个慢指针，两个慢指针一起走，再次相遇时，则是环的入口。
- 234. 回文链表：实际上也是找到链表的中间位置，然后去判断是否为回文。判断回文的逻辑，借助栈或者反转后半段链表都可以。
- 148. 排序链表：在使用归并排序时，也是通过快慢指针找到每个子链表的中间节点，去归并处理。
因为没有办法获取链表的长度，对于寻找倒数第 n 个节点的问题时，这种方法可以一次遍历找到目标节点。
典型题目：
- 19. 删除链表的倒数第 N 个结点：一个指针先走 n 步，然后两个指针同时前进，当先出发指针遍历完成时，后出发指针就在倒数第 n 个节点。
- 61. 旋转链表：与上一题类似，只是先走的 n 步可能会超过链表的总长度，需要取模处理一下。
反转链表
反转链表主要有递归法和迭代法两种解决方法，因为指针指来指去的容易晕头转向，所以在这里记录标准的解答代码。
public ListNode reverseList(ListNode head) {
// 这个head就是原链表的最后一个节点，也是反转后链表的新节点
if (head == null || head.next == null) {
return head;
}
// 本质上，resultNode就是递归到最深处后，一层层返回的新链表的头结点
ListNode resultNode = reverseList(head.next);
head.next.next = head;
head.next = null;
return resultNode;
}
public ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode pre = null;
ListNode next;
while (current != null) {
next = current.next;
current.next = pre;
pre = current;
current = next;
}
return pre;
}
LRU缓存
而在读写方面，缓存是有要求的：函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
为了达成这个要求，底层的数据结构需要用链表来实现。
所以我们实现的 LRU 底层的数据结构是：HashMap +链表。
代码如下，虽然不够优雅，但是方便理解逻辑。
public class LRUCache {
private int maxSize = 0;
private Node head = new Node();
private Node tail = head;
HashMap map = new HashMap<>();
public LRUCache(int capacity) {
this.maxSize = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
// get也是使用了该值，因此需要将该值更新到最近使用的位置
updateNode(node);
return node.value;
}
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
updateNode(node);
return;
}
// 新插入的值放到链尾
Node node = new Node(key, value);
node.prev = tail;
map.put(key, node);
tail.next = node;
tail = node;
if (map.size() > maxSize) {
// 此时需要移除最久未使用数据值
Node removed = head.next;
head.next = removed.next;
head.next.prev = head;
map.remove(removed.key);
}
}
private void updateNode(Node current) {
// 如果当前节点已经是尾节点，则不需要移动
if (current.next == null) {
return;
}
// 当前节点的前节点指向当前节点的后节点，即原链表中删除该节点
current.prev.next = current.next;
current.next.prev = current.prev;
// 当前节点放到尾节点
current.prev = tail;
current.next = null;
tail.next = current;
// 尾节点移动
tail = current;
}
class Node {
public int key;
public int value;
public Node prev;
public Node next;
public Node(){}
public Node(int key,int value) {
this.key = key;
this.value = value;
}
}
}
Original: https://www.cnblogs.com/codeflyer/p/16398419.html
Author: 小白码上飞
Title: 链表算法题解题技巧归纳总结
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/714806/
转载文章受原作者版权保护。转载请注明原作者出处！