面试必备：高频算法题汇总「图文解析 + 教学视频 + 范例代码」必问之链表 + 栈 + 队列部分！

圆号本昊

发布于 2021-09-24 11:51:04

2360

发布于 2021-09-24 11:51:04

文章被收录于专栏：github@hornhuang

链表

链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。

综合多方面的原因，链表题目在面试中占据着很重要的地位。

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理它，让我们简单地转到前面的子表达式。
如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个相同类型的左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

视频

英文：【编程】字符串中括号平衡判断（HackerRank）

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 == ']');
}

用栈实现队列

思路：

思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。
数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得取栈底元素，那么辅助栈就派上用场了
把数据栈的元素依次弹出到辅助栈，但保留最后一个元素，最后数据栈就剩下了最后一个元素，直接把元素返回，这时数据栈已经没有了数据。
最后呢，把辅助栈的元素依次压人数据栈，这样，我们成功取到了栈底元素。

视频

图解「剑指Offer」之使用栈实现队列

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();
}

重点

为了提高文章质量，防止冗长乏味

下一部分算法题

本片文章篇幅总结越长。我一直觉得，一片过长的文章，就像一堂超长的会议/课堂，体验很不好，所以我打算再开一篇文章
在后续文章中，我将继续针对链表 栈 队列 堆 动态规划 矩阵 位运算 等近百种，面试高频算法题，及其图文解析 + 教学视频 + 范例代码，进行深入剖析有兴趣可以继续关注 _yuanhao 的编程世界
不求快，只求优质，每篇文章将以 2 ～ 3 天的周期进行更新，力求保持高质量输出