🔥 面试必备：高频算法题汇总「图文解析 + 教学视频 + 范例代码」必问之 链表 + 栈 + 队列 部分！🔥
- 2019 年 10 月 13 日
- 筆記
链表
链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。
综合多方面的原因，链表题目在面试中占据着很
重要的地位。
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }删除节点
思路：
- 将
下一个节点复制到当前
public void deleteNode(ListNode node) { if (node.next == null){ node = null; return; } // 取缔下一节点 node.val = node.next.val node.next = node.next.next }翻转链表
思路
思路：每次都将原第一个结点之后的那个结点放在新的表头后面。
比如1,2,3,4,5
- 第一次：把第一个
结点1后边的结点2放到新表头后面，变成2,1,3,4,5 - 第二次：把第一个
结点1后边的结点3放到新表头后面，变成3,2,1,4,5 - ……
- 直到： 第一个
结点1，后边没有结点为止。
视频
大圣算法 翻转链表(Reverse Linked List ) — LeetCode 206
public ListNode reverse(ListNode head) { //prev表示前继节点 ListNode prev = null; while (head != null) { //temp记录下一个节点，head是当前节点 ListNode temp = head.next; head.next = prev; prev = head; head = temp; } return prev; }中间元素
思路
我总结了一下，可以称为 田忌赛马’法
public ListNode findMiddle(ListNode head){ if(head == null){ return null; } ListNode slow = head; ListNode fast = head; // fast.next = null 表示 fast 是链表的尾节点 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }合并两个已排序链表
思路
- 递归方法：首先比较给新链表
接上一个结点，然后这个结点的next就是剩下的两条链表合并的结果。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode lastNode = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { lastNode.next = l1; l1 = l1.next; } else { lastNode.next = l2; l2 = l2.next; } lastNode = lastNode.next; } if (l1 != null) { lastNode.next = l1; } else { lastNode.next = l2; } return dummy.next; }链表排序
归并排序
-
归并排序的也是基于分治的思想，但是与快排不同的是归并是先划分，然后从底层开始向上合并。 -
归并排序的主要思想是将两个
已经排好序的分段合并成一个有序的分段。除了找到中间节点的操作必须遍历链表外，其它操作与数组的归并排序基本相同。
视频
public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } // 取得中间节点，将链表一分为二 ListNode mid = findMiddle(head); ListNode right = sortList(mid.next); mid.next = null; ListNode left = sortList(head); return mergeTwoLists(left, right); } // 查找中间元素算法 public ListNode findMiddle(ListNode head){ if(head == null){ return null; } ListNode slow = head; ListNode fast = head; // fast.next = null 表示 fast 是链表的尾节点 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } // 合并两个有序链表 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode lastNode = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { lastNode.next = l1; l1 = l1.next; } else { lastNode.next = l2; l2 = l2.next; } lastNode = lastNode.next; } if (l1 != null) { lastNode.next = l1; } else { lastNode.next = l2; } return dummy.next; }快速排序
快速排序的主要思想是：
-
选定一个
基准元素 -
经过一趟排序，将所有元素分成
两部分 -
分别对两部分重复上述操作，直到所有元素都已排序成功
因为单链表只能从链表头节点向后遍历，没有prev指针，因此必须选择头节点作为基准元素。这样第二步操作的时间复杂度就为O(n)。由于之后都是分别对两部分完成上述操作，因此会将链表划分为lgn个段，因此时间复杂度为O(nlgn）
public ListNode sortList(ListNode head) { quickSort(head, null); return head; } private void quickSort(ListNode start, ListNode end) { if (start == end) { return; } ListNode pt = partition(start, end); quickSort(start, pt); quickSort(pt.next, end); } // 快排 轮状法 private ListNode partition(ListNode start, ListNode end) { int pivotKey = start.val; ListNode p1 = start, p2 = start.next; while (p2 != end) { if (p2.val < pivotKey) { p1 = p1.next; swapValue(p1, p2); } p2 = p2.next; } swapValue(start, p1); return p1; } private void swapValue(ListNode node1, ListNode node2) { int tmp = node1.val; node1.val = node2.val; node2.val = tmp; }两个链表是否相交
思路
-
如果两个单链表有
共同的节点 -
那么从第一个节点开始，后面的节点都会
重叠，直至链表结束 -
因为两个链表中有一个
共同节点 -
则从这个节点里的
指针域指向下一个节点的地址就相同 -
所以
相交以后的节点就会相同，直至链表结束，总的模型就像一个“Y”
视频
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode currA = headA; ListNode currB = headB; int lengthA = 0; int lengthB = 0; // 让长的先走到剩余长度和短的一样 while (currA != null) { currA = currA.next; lengthA++; } while (currB != null) { currB = currB.next; lengthB++; } currA = headA; currB = headB; while (lengthA > lengthB) { currA = currA.next; lengthA--; } while (lengthB > lengthA) { currB = currB.next; lengthB--; } // 然后同时走到第一个相同的地方 while (currA != currB) { currA = currA.next; currB = currB.next; } // 返回交叉开始的节点 return currA; }栈 / 队列
- 栈（stack）又名堆栈：
它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
- 队列是一种特殊的线性表
特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
带最小值操作的栈
这道面试题主要考察我们对于辅助栈的使用。
常见的辅助栈包括两种：
-
辅助栈和数据栈同步
-
辅助栈和数据栈不同步
我们这里采用辅助栈和数据栈同步的方式：
特点：编码简单，不用考虑一些边界情况，就有一点不好：辅助栈可能会存一些“不必要”的元素。
-
辅助栈为空的时候，必须放入新进来的数；
-
新来的数小于或者等于辅助栈栈顶元素的时候，才放入，特别注意这里“等于”要考虑进去，因为出栈的时候，连续的、相等的并且是最小值的元素要同步出栈；
-
出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈。
总结一下：出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。
public class MinStack { private Stack<Integer> stack; private Stack<Integer> minStack; // 维护一个辅助栈，传入当前栈的最小值 public MinStack() { stack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int number) { stack.push(number); if (minStack.isEmpty()) { minStack.push(number); } else { minStack.push(Math.min(number, minStack.peek())); } } public int pop() { minStack.pop(); return stack.pop(); } public int min() { return minStack.peek(); } }有效括号
思路：
-
初始化栈 S。
-
一次处理表达式的每个括号。
-
如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处4理它，让我们简单地转到前面的 子表达式。
-
如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
-
如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。
视频
public boolean isValidParentheses(String s) { Stack<Character> stack = new Stack<Character>(); for (Character c : s.toCharArray()) { if ("({[".contains(String.valueOf(c))) { stack.push(c); } else { if (!stack.isEmpty() && isValid(stack.peek(), c)) { stack.pop(); } else { return false; } } } return stack.isEmpty(); } private boolean isValid(char c1, char c2) { return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}') || (c1 == '[' && c2 == ']'); }用栈实现队列
思路：
-
思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。
-
数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了
-
把数据栈的元素依次弹出到辅助栈，但保留最后一个元素，最后数据栈就剩下了最后一个元素，直接把元素返回，这时数据栈已经没有了数据。
-
最后呢，把辅助栈的元素依次压人数据栈，这样，我们成功取到了栈底元素。
视频
public class MyQueue { private Stack<Integer> outStack; private Stack<Integer> inStack; public MyQueue() { outStack = new Stack<Integer>(); inStack = new Stack<Integer>(); } private void in2OutStack(){ while(!inStack.isEmpty()){ outStack.push(inStack.pop()); } } public void push(int element) { inStack.push(element); } public int pop() { if(outStack.isEmpty()){ this.in2OutStack(); } return outStack.pop(); } public int top() { if(outStack.isEmpty()){ this.in2OutStack(); } return outStack.peek(); } }逆波兰表达式求值 (后缀)
思路：
-
逆波兰表达式求解,定义一个栈辅助计算
-
当遇到运算符"+"、"-"、"*"、"/"时,从栈中pop出两个数字计算,否则将数字入栈;
public int evalRPN(String[] tokens) { Stack<Integer> s = new Stack<Integer>(); String operators = "+-*/"; for (String token : tokens) { if (!operators.contains(token)) { s.push(Integer.valueOf(token)); continue; } // 这里有个坑 int a = s.pop(); int b = s.pop(); // 先出的在运算符后 // 后出的在运算符前 if (token.equals("+")) { s.push(b + a); } else if(token.equals("-")) { s.push(b - a); } else if(token.equals("*")) { s.push(b * a); } else { s.push(b / a); } } return s.pop(); }Attention
为了提高文章质量，防止冗长乏味
下一部分算法题
-
本片文章篇幅总结越长。我一直觉得，一片过长的文章，就像一场超长的 会议/课堂，体验很不好，所以打算再开一篇文章来总结其余的考点
-
在后续文章中，我将继续针对
链表栈队列堆动态规划矩阵位运算等近百种，面试高频算法题，及其图文解析 + 教学视频 + 范例代码，进行深入剖析有兴趣可以继续关注 _yuanhao 的编程世界
相关文章
?面试必备：高频算法题汇总「图文解析 + 教学视频 + 范例代码」必知必会 排序 + 二叉树 部分！?
每个人都要学的图片压缩终极奥义，有效解决 Android 程序 OOM
Android 让你的 Room 搭上 RxJava 的顺风车 从重复的代码中解脱出来
ViewModel 和 ViewModelProvider.Factory：ViewModel 的创建者
单例模式-全局可用的 context 对象，这一篇就够了
缩放手势 ScaleGestureDetector 源码解析，这一篇就够了
Android 属性动画框架 ObjectAnimator、ValueAnimator ，这一篇就够了
看完这篇再不会 View 的动画框架，我跪搓衣板
看完这篇还不会 GestureDetector 手势检测，我跪搓衣板！
android 自定义控件之-绘制钟表盘
欢迎关注_yuanhao的博客园！
为了方便大家跟进学习，我在 GitHub 建立了一个仓库
仓库地址：超级干货！精心归纳视频、归类、总结，各位路过的老铁支持一下！给个 Star ！
