最近集中研究了一批链表题。在这里我总结了解决问题的技巧和相应的解决问题的思路。
解题思路不会一丝不苟,主要是总结和分类,希望能用几句话来激发灵感,正确的应该是没有思路时的指导和提纲,以备日后复习。
还有一些经典的话题很重要或者总是头晕,代码的实现逻辑也记录在这里。
一、解决链表问题的两种技巧
遇到链表相关的问题,不管是什么问题,先想想能不能用下面两个技巧。
哨兵节点双指针1、哨兵节点
哨兵节点是一种很常见的链表技巧,可以在处理链表边界问题的情况下降低我们代码的复杂度。主要需要解决的问题如下:
处理完一个链表后,需要返回链表的头节点。我们首先使用一个哨兵节点(虚拟),它的下一个节点指向头节点。只需在最终返回中直接返回 dummy.next 即可。在链表中插入或删除节点时,使用哨兵节点可以简化删除头节点或在头前插入节点时的处理逻辑。遍历链表时,可能需要同时记录前置节点。当你从头节点开始遍历时,头没有前置节点(它为空)。这时引用哨兵节点就相当于帮头节点初始化一个pre节点,可以轻松解决pre节点为空的问题。
由于哨兵节点的使用场景非常广泛,这里不列出典型的话题。
2、双指针
双指针真的很有用。事实上,它不仅是一个链表,而且对于数组问题来说也是一种非常有用的技术。
双指针的主要用途如下:
两个指针在两个链表上行走。快速和慢速指针同时向前和向后移动。前指针先移动 n 步,然后两个指针同时向前移动。两个指针在两个链表上行走。
有时,您需要将两个链表合并为一个链表,或者将一个链表拆分为两个链表。此时就需要使用两个指针在两个链表上行走,进行逻辑处理。
典型主题:
快慢指针
快指针的速度是慢指针的n倍,那么当快指针用完时,慢指针停留的位置是整个链表的1/n(近似位置)。正常情况下,慢指针走一步,快指针走两步。
典型主题:
指针先走 n 步
因为没有办法得到链表的长度,所以对于查找倒数第n个节点的问题,这种方法可以一次遍历找到目标节点。
典型主题:
二、经典链表问题的解决方案 反转链表
206. 反转链表是最经典的链表问题。除了高级问题92.反向链表II,反向链表也将用于其他链表问题的答案,例如上面提到的234.回文链表。
反转链表主要有两种解决方案:递归法和迭代法。因为指针容易混淆,所以这里记录标准的解决方案代码。
递归
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 缓存
146. LRU缓存毕竟是缓存,必须是键值对的结构,所以使用了HashMap。
在读写方面,缓存是必需的: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;
}
}
}
暂无评论内容