链表算法题解题技巧归纳总结
2022/6/22 1:19:52
本文主要是介绍链表算法题解题技巧归纳总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最近集中刷了一批链表的题型,在这里总结一下解题技巧,以及对应题目的解题思路。
解题思路并不会细致入微,主要是为了总结归类,并且希望用几句话来激发灵感,权当是没思路时的指引以及以后复习时的提纲了。
还有一些重要或者总会绕晕的经典题目,也在这里记录一下代码的实现逻辑。
一、解决链表题型的两个技巧
遇到链表相关的题,无论问题是什么,先要想想是不是可以用上以下的两个技巧。
- 哨兵节点
- 双指针
1、哨兵节点
哨兵节点是一个非常常用的链表技巧,在处理链表边界问题的场景下,可以减少我们代码的复杂度。主要解决的问题如下:
- 处理完一条链表后,需要返回这个链表的头结点。我们在一开始的时候使用哨兵节点(dummy),让它的 next 节点指向 head 节点。最后 return 时直接返回 dummy.next 即可。
- 在对链表进行插入或删除节点时,使用哨兵节点可以简化删除 head 节点或者向 head 前插入节点时的处理逻辑。
- 在某些遍历链表的时候,可能会需要同时记录 pre 节点。当你从 head 节点开始遍历时,head 是没有 pre 节点的(为null)。而此时引用哨兵节点,相当于帮助 head 节点初始化了一个 pre 节点,可以方便的解决 pre 节点为空的问题。
因为哨兵节点使用场景很广泛,所以在这里就不针对性的列出典型题目了。
2、双指针
双指针实在是太好用了,其实不止是链表,对于数组题来说,也是非常好用的技巧。
双指针的主要用法有以下几种:
- 两个指针在两条链表上行走
- 快慢指针,同时前进
- 前后指针,前指针先走 n 步,之后两个指针同时前进
两个指针在两条链表上行走
有时,你需要将两条链表合并成一条链表,或者要将一条链表拆分成两条链表。此时,需要用两个指针分别在两条链表上行走,并处理逻辑。
典型题目:
-
21. 合并两个有序链表:两个指针在两条链表上行走,哪个指针指向的节点值大,则将该节点放到合并后的链表上,指针继续向前一步。
-
86. 分隔链表:根据指定的目标值,将一个链表先分割成两个链表。因此,需要两个指针在分割出来的两个链表上行走。之后再将两个链表直接头尾合并。
-
160. 相交链表:两个指针在两条链表上行走,当一个指针指向当前列表的结尾时,继续遍历另外一个链表。这样可以保证两个指针指向相同的节点时,这个节点就是相交节点。
快慢指针
快指针的速度是慢指针 n 倍,则当快指针走完时,慢指针停留的地方就是整个链表的 1/n 处(大概位置)。一般情况下都是慢指针走一步,快指针走两步。
典型题目:
-
876. 链表的中间结点:快指针走两步,慢指针走一步。快指针走到结尾时,则慢指针在中间位置。
-
141. 环形链表:快指针走两步,慢指针走一步。当快慢指针相遇时,从头结点再出发一个慢指针,两个慢指针一起走,再次相遇时,则是环的入口。
-
234. 回文链表:实际上也是找到链表的中间位置,然后去判断是否为回文。判断回文的逻辑,借助栈或者反转后半段链表都可以。
-
148. 排序链表:在使用归并排序时,也是通过快慢指针找到每个子链表的中间节点,去归并处理。
一个指针先走 n 步
因为没有办法获取链表的长度,对于寻找倒数第 n 个节点的问题时,这种方法可以一次遍历找到目标节点。
典型题目:
-
19. 删除链表的倒数第 N 个结点:一个指针先走 n 步,然后两个指针同时前进,当先出发指针遍历完成时,后出发指针就在倒数第 n 个节点。
-
61. 旋转链表:与上一题类似,只是先走的 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<Integer, Node> 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; } } }
这篇关于链表算法题解题技巧归纳总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)