跳至主要內容

94道Java数据结构高频核心面试题

江小北2025年5月7日大约 100 分钟Java 6530+道面试题java

   免费赠送 :《Java面试宝典》 持续更新+ 史上最全 + 面试必备 2000页 + 大厂必备 +涨薪必备]

94道Java数据结构高频核心面试题

1- 简述什么是Java优先级队列 (Priority Queue)？

Java中的优先级队列（Priority Queue）是一种特殊的队列数据结构，它根据元素的优先级来决定出队顺序。与普通队列按照先进先出（FIFO）原则不同，优先级队列总是将具有最高优先级的元素排在最前面，当执行出队操作时，返回的是当前队列中优先级最高的元素。

主要特点：

  1. 基于优先级：元素按照优先级顺序进行排序。对于实现了Comparable接口的对象，默认情况下，优先级是按自然顺序排列的；也可以通过自定义比较器（Comparator）来指定优先级规则。
  2. 不保证插入顺序：虽然内部使用堆（Heap）实现以保持高效的插入和删除操作，但并不保证相同优先级元素之间的相对顺序。
  3. 无界队列：理论上可以存储任意数量的元素，但在实际应用中可能会受到系统资源或配置限制。
  4. 不允许null值：试图添加null元素会抛出NullPointerException异常。
  5. 非线程安全：如果需要在多线程环境中使用，则应考虑外部同步机制或者选择线程安全的替代方案，如PriorityBlockingQueue。

常用方法：

  • add(E e) / offer(E e)：向队列中插入一个元素，并根据其优先级自动调整位置。
  • peek()：查看队列头部（最高优先级）元素而不移除它。
  • poll()：移除并返回队列头部（最高优先级）元素；如果队列为空则返回null。
  • size()：获取队列中元素的数量。

总之，Java的优先级队列为开发者提供了一种灵活且高效的方式来管理带有不同优先级的任务或其他对象。

2-请描述大O符号(big-O notation)的作用？

大O符号（Big-O notation）是计算机科学和数学中用于描述算法效率或复杂度的一种表示方法。它主要用于分析算法在最坏情况下的时间复杂度或空间复杂度，帮助我们理解算法随着输入规模增长时的性能表现。

1. 作用

  • 衡量算法效率：大O符号用来衡量算法的时间复杂度（执行时间）和空间复杂度（占用内存）。它关注的是算法在处理大规模数据时的表现，而不是具体的运行时间。
  • 忽略常数项和低阶项：大O符号只保留影响最大的项，忽略常数因子和低阶项。例如，O(n² + n) 简化为 O(n²)，因为当 n 很大时，n² 的增长速度远快于 n。
  • 比较不同算法的优劣：通过大O符号，可以方便地比较不同算法的效率。例如，O(log n) 的算法通常比 O(n) 的算法更高效，尤其是在处理大规模数据时。
  • 简化分析：大O符号提供了一种简化的、抽象的方式来分析算法，使得开发者可以专注于算法的增长趋势，而不是具体的硬件或实现细节。

2. 常见的大O复杂度

  • O(1)：常数时间复杂度，表示算法的执行时间和输入规模无关。例如，访问数组中的某个元素。
  • O(log n)：对数时间复杂度，表示算法的执行时间与输入规模呈对数关系。例如，二分查找。
  • O(n)：线性时间复杂度，表示算法的执行时间与输入规模成正比。例如，遍历数组。
  • O(n log n)：线性对数时间复杂度，常见于高效的排序算法，如归并排序和快速排序。
  • O(n²)：平方时间复杂度，表示算法的执行时间与输入规模的平方成正比。例如，嵌套循环的两层遍历。
  • O(2^n)：指数时间复杂度，表示算法的执行时间随着输入规模呈指数增长。例如，某些递归算法。
  • O(n!)：阶乘时间复杂度，表示算法的执行时间随着输入规模呈阶乘增长。例如，暴力求解旅行商问题。

3. 应用场景

  • 算法设计与优化：在设计算法时，开发者可以通过大O符号评估不同算法的效率，并选择最优的解决方案。
  • 性能瓶颈分析：通过大O符号，可以识别出算法中可能导致性能瓶颈的部分，并进行优化。
  • 系统扩展性评估：在构建大型系统时，了解算法的复杂度有助于评估系统的扩展性和可维护性。

总之，大O符号为我们提供了一个简洁且强大的工具，用于分析和比较算法的效率，从而帮助我们在实际应用中做出更好的选择。
深度讲解面试题：简述什么是Java优先级队列( Priority Queue ) ？
Java中的优先级队列（Priority Queue）是一种特殊的队列数据结构，它根据元素的优先级来决定出队顺序。与普通队列按照先进先出（FIFO）原则不同，优先级队列总是将具有最高优先级的元素排在最前面，当执行出队操作时，返回的是当前队列中优先级最高的元素。

主要特点：

  1. 基于优先级：元素按照优先级顺序进行排序。对于实现了Comparable接口的对象，默认情况下，优先级是按自然顺序排列的；也可以通过自定义比较器（Comparator）来指定优先级规则。
  2. 不保证插入顺序：虽然内部使用堆（Heap）实现以保持高效的插入和删除操作，但并不保证相同优先级元素之间的相对顺序。
  3. 无界队列：理论上可以存储任意数量的元素，但在实际应用中可能会受到系统资源或配置限制。
  4. 不允许null值：试图添加null元素会抛出NullPointerException异常。
  5. 非线程安全：如果需要在多线程环境中使用，则应考虑外部同步机制或者选择线程安全的替代方案如PriorityBlockingQueue。

常用方法：

  • add(E e) / offer(E e)：向队列中插入一个元素，并根据其优先级自动调整位置。
  • peek()：查看队列头部（最高优先级）元素而不移除它。
  • poll()：移除并返回队列头部（最高优先级）元素；如果队列为空则返回null。
  • size()：获取队列中元素的数量。
    总之，Java的优先级队列为开发者提供了一种灵活且高效的方式来管理带有不同优先级的任务或其他对象。

8-编写Java代码实现循环队列

循环队列（Circular Queue）是一种线性数据结构，但它的操作是基于循环的方式进行的。当队列的尾部达到数组的末尾时，它会绕回到数组的开头。这种设计可以更高效地利用内存空间。

下面是一个用Java实现的简单循环队列：

public class CircularQueue {
    private int front; // 队首指针
    private int rear; // 队尾指针
    private int capacity; // 队列容量
    private int[] queue; // 存储队列元素的数组
    private int count; // 当前队列中的元素数量

    // 构造函数，初始化队列
    public CircularQueue(int size) {
        this.capacity = size;
        this.queue = new int[size];
        this.front = 0;
        this.rear = -1;
        this.count = 0;
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return count == 0;
    }

    // 检查队列是否已满
    public boolean isFull() {
        return count == capacity;
    }

    // 入队操作
    public void enqueue(int item) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        rear = (rear + 1) % capacity;
        queue[rear] = item;
        count++;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        front = (front + 1) % capacity;
        count--;
        return item;
    }

    // 获取队首元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }

    // 获取队列大小
    public int size() {
        return count;
    }

    // 打印队列内容
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        for (int i = 0; i < count; i++) {
            int index = (front + i) % capacity;
            System.out.print(queue[index] + " ");
        }
        System.out.println();
    }

    // 测试循环队列
    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(5);
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        System.out.println("Initial queue: ");
        q.printQueue();

        q.dequeue();
        q.dequeue();
        System.out.println("After two dequeues: ");
        q.printQueue();

        q.enqueue(6);
        q.enqueue(7);
        System.out.println("After adding 6 and 7: ");
        q.printQueue();

        try {
            q.enqueue(8); // 这里应该抛出异常，因为队列已满
        } catch (RuntimeException e) {
            System.out.println(e.getMessage());
        }
    }
}

解释：

  1. 构造函数：初始化队列的容量、数组、前后指针和计数器。
  2. 入队 (enqueue)：将元素插入到队尾。如果队列已满，则抛出异常。
  3. 出队 (dequeue)：移除并返回队首元素。如果队列为空，则抛出异常。
  4. 检查空和满：通过 count 变量来判断队列是否为空或已满。
  5. 获取队首元素 (peek)：返回队首元素而不移除它。
  6. 获取队列大小 (size)：返回当前队列中的元素数量。
  7. 打印队列内容 (printQueue)：遍历队列并打印所有元素。

注意事项：

  • front 和 rear 的更新使用了模运算 (%) 来实现循环特性。
  • count 用于跟踪当前队列中的元素数量，避免了空与满状态的混淆问题（即 front == rear 的情况）。

9-编写Java代码实现链队列

链队列是一种基于链表实现的队列数据结构。它通过节点来存储元素，每个节点包含数据和指向下一个节点的引用。以下是用Java实现链队列的代码示例：

// 定义链队列中的节点类
class Node {
    int data; // 节点存储的数据
    Node next; // 指向下一个节点的引用

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 定义链队列类
class LinkedQueue {
    private Node front; // 队首指针
    private Node rear; // 队尾指针
    private int size; // 队列中元素的数量

    // 构造函数初始化队列
    public LinkedQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == null;
    }

    // 获取队列的大小
    public int size() {
        return size;
    }

    // 入队操作
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) { // 如果队列为空，front和rear都指向新节点
            front = newNode;
            rear = newNode;
        } else { // 否则将新节点添加到rear后面，并更新rear
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 出队操作
    public int dequeue() throws Exception {
        if (isEmpty()) {
            throw new Exception("Queue is empty");
        }
        int data = front.data; // 获取队首元素
        front = front.next; // 将front指针后移
        if (front == null) { // 如果front为null，说明队列已空，更新rear
            rear = null;
        }
        size--;
        return data;
    }

    // 获取队首元素
    public int peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("Queue is empty");
        }
        return front.data;
    }

    // 打印队列中的所有元素
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        Node current = front;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

// 测试链队列的功能
public class Main {
    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        try {
            queue.enqueue(10);
            queue.enqueue(20);
            queue.enqueue(30);
            queue.display(); // 输出：10 20 30

            System.out.println("Dequeue: " + queue.dequeue()); // 输出：Dequeue: 10
            queue.display(); // 输出：20 30

            System.out.println("Front element: " + queue.peek()); // 输出：Front element: 20
            queue.display(); // 输出：20 30

            System.out.println("Queue size: " + queue.size()); // 输出：Queue size: 2
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}

代码说明：

  1. Node 类：定义了链队列中的节点结构，包含数据域 data 和指针域 next。
  2. LinkedQueue 类：实现了链队列的基本操作，包括入队 (enqueue)、出队 (dequeue)、获取队首元素 (peek)、判断队列是否为空 (isEmpty) 和获取队列大小 (size)。
  3. Main 类：测试链队列的功能，展示了如何使用链队列。

运行结果示例：

10 20 30
Dequeue: 10
20 30
Front element: 20
20 30
Queue size: 2

通过上述代码，你可以轻松地创建和操作一个基于链表的队列。

10. 简述Java单链表的基本概念？

Java中的单链表是一种线性数据结构，它由一系列节点（Node）组成。每个节点包含两个主要部分：存储元素的数据域和指向下一个节点的引用（指针）。单链表的特点是每个节点只知道它的下一个节点的位置，而不知道前一个节点的位置，最后一个节点的引用为null，表示链表的结束。

基本概念

  1. 节点(Node)：链表的基本组成部分，每个节点包括两部分，一是存储的数据，二是指向下一个节点的链接。
  2. 头结点(Head Node)：链表的第一个节点称为头结点。如果链表为空，则头结点为null。
  3. 尾结点(Tail Node)：链表的最后一个节点，其next域为null。
  4. 遍历(Traversal)：从头结点开始，沿着每个节点的链接依次访问每一个节点，直到遇到尾结点。

操作

  • 插入(Insertion)：可以在链表的头部、尾部或者指定位置插入新节点。
  • 删除(Deletion)：可以删除链表中特定位置的节点，或者是具有特定值的第一个节点。
  • 查找(Search)：遍历链表以找到特定值的节点。
  • 更新(Update)：找到特定节点并修改其内容。
  • 反转(Reverse)：改变所有节点的链接方向，使链表中的元素顺序颠倒。

优点

  • 动态大小：可以根据需要增加或减少节点，不需要预先定义固定大小。
  • 方便的插入和删除操作：在链表中插入或删除元素时，只需更改相关节点的链接即可，无需移动其他元素。

缺点

  • 随机访问效率低：不像数组那样可以直接通过索引访问元素，必须从头开始遍历，时间复杂度为O(n)。
  • 额外的空间开销：每个节点除了存储数据外，还需要额外的空间来存储指向下一个节点的引用。

在Java中，可以通过自定义类来实现单链表，也可以直接使用Java标准库中的LinkedList类，但需要注意的是，java.util.LinkedList实际上是一个双向链表，并且实现了List和Deque接口，提供了更多的功能。

11-编写Java代码实现单链表

下面是一个简单的Java代码实现单链表（Singly Linked List）。我们将定义一个Node类来表示链表中的节点，以及一个SinglyLinkedList类来管理链表的操作。

1. 定义 Node 类

每个节点包含两个部分：数据（data）和指向下一个节点的引用（next）。

class Node {
    int data;
    Node next;

    // 构造函数
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

2. 定义 SinglyLinkedList 类

这个类将包含对链表的各种操作，比如插入、删除、遍历等。

public class SinglyLinkedList {
    private Node head; // 链表的头节点

    // 构造函数
    public SinglyLinkedList() {
        this.head = null;
    }

    // 插入新节点到链表的末尾
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 在链表头部插入新节点
    public void prepend(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 删除指定值的节点
    public void delete(int key) {
        // 如果头节点就是要删除的节点
        if (head != null && head.data == key) {
            head = head.next;
            return;
        }

        // 查找要删除的节点
        Node current = head;
        while (current != null && current.next != null) {
            if (current.next.data == key) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 查找链表中是否包含某个值
    public boolean contains(int key) {
        Node current = head;
        while (current != null) {
            if (current.data == key) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 打印链表中的所有元素
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 获取链表的长度
    public int length() {
        int count = 0;
        Node current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    // 主方法用于测试
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();

        // 插入一些元素
        list.append(10);
        list.append(20);
        list.prepend(5);
        list.append(30);

        // 打印链表
        System.out.println("链表内容: ");
        list.printList();

        // 检查链表中是否包含某个值
        System.out.println("链表中是否包含20: " + list.contains(20));
        System.out.println("链表中是否包含15: " + list.contains(15));

        // 删除节点
        list.delete(20);
        System.out.println("删除20后的链表: ");
        list.printList();

        // 获取链表长度
        System.out.println("链表的长度: " + list.length());
    }
}

代码解释：

  1. Node 类：每个节点包含一个整数数据和一个指向下一个节点的引用。
  2. SinglyLinkedList 类：管理链表的操作，包括：
    • append(int data)：在链表末尾添加新节点。
    • prepend(int data)：在链表头部添加新节点。
    • delete(int key)：删除链表中包含指定值的节点。
    • contains(int key)：检查链表中是否包含某个值。
    • printList()：打印链表中的所有元素。
    • length()：返回链表的长度。

测试输出：

运行上述代码后，输出可能如下：

链表内容:
5 -> 10 -> 20 -> 30 -> null
链表中是否包含20: true
链表中是否包含15: false
删除20后的链表:
5 -> 10 -> 30 -> null
链表的长度: 3

12 - 简述 Java 双向链表基本概念

Java 中的双向链表（Doubly Linked List）是一种线性数据结构，它由一系列节点组成，每个节点包含三个部分：存储数据元素的数据域、指向前一个节点的引用（前驱指针）和指向后一个节点的引用（后继指针）。这种结构允许在两个方向上遍历链表，并且在插入或删除节点时只需调整相邻节点的引用关系，而无需移动节点本身。

在 Java 中，java.util.LinkedList 类实现了双向链表。它不仅实现了 List 接口，还实现了 Deque（双端队列）接口，这使得它可以作为列表和队列使用。以下是双向链表的一些基本概念：

  1. 节点（Node）：
    每个节点包含三个部分：

    • 数据域（Element Data）：用于存储实际的数据。
    • 前驱指针（Previous Pointer）：指向链表中前一个节点。
    • 后继指针（Next Pointer）：指向链表中后一个节点。

  2. 头节点（Head Node）和尾节点（Tail Node）：
    链表的第一个节点称为头节点，最后一个节点称为尾节点。对于空链表，头节点和尾节点都为 null。

  3. 遍历（Traversal）：
    由于每个节点都有前后指针，因此可以从头到尾或从尾到头遍历链表。例如，使用 for-each 循环或者迭代器 Iterator 进行遍历。

  4. 插入（Insertion）：
    可以在链表的任意位置插入新节点，最常见的是在头部、尾部或指定位置插入。插入操作需要更新相邻节点的前后指针。

  5. 删除（Deletion）：
    可以删除链表中的任意节点，通常需要先找到目标节点，然后调整其前后节点的指针，使其绕过目标节点。如果删除的是头节点或尾节点，则需特别处理。

  6. 查找（Search）：
    可以通过遍历链表来查找特定值的节点，时间复杂度为 O(n)，其中 n 是链表长度。

  7. 优点与缺点：

    • 优点：
      • 插入和删除操作效率高，不需要像数组那样移动大量元素。
      • 双向链表支持双向遍历。
    • 缺点：
      • 额外的空间开销，因为每个节点需要存储两个指针。
      • 随机访问效率低，无法像数组那样通过索引快速定位元素。

  8. 应用场景：

    • 适合频繁插入和删除场景。
    • 实现栈、队列等抽象数据类型。
    • 缓存机制（如 LRU 缓存）。

总之，双向链表是一种灵活且高效的线性数据结构，在许多实际应用中具有重要作用。Java 提供的 LinkedList 类封装了这些底层实现细节，使得开发者可以直接使用丰富的 API 来操作双向链表。

13-编写Java代码实现双向链表

下面是一个使用Java实现的双向链表（Doubly Linked List）代码示例。双向链表中的每个节点包含三个部分：数据、指向前一个节点的引用和指向下一个节点的引用。

// 定义双向链表的节点类
class Node {
    int data; // 节点存储的数据
    Node prev; // 指向前一个节点的引用
    Node next; // 指向后一个节点的引用

    // 构造函数
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// 定义双向链表类
class DoublyLinkedList {
    private Node head; // 链表头节点
    private Node tail; // 链表尾节点

    // 构造函数
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 在链表末尾添加节点
    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) { // 如果链表为空，新节点成为头节点
            head = newNode;
            tail = newNode;
        } else { // 否则将新节点添加到链表末尾
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 删除指定数据的节点
    public void deleteNode(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                if (current.prev != null) { // 如果不是头节点
                    current.prev.next = current.next;
                } else { // 如果是头节点
                    head = current.next;
                }
                if (current.next != null) { // 如果不是尾节点
                    current.next.prev = current.prev;
                } else { // 如果是尾节点
                    tail = current.prev;
                }
                return;
            }
            current = current.next;
        }
    }

    // 打印链表内容
    public void printList() {
        Node current = head;
        System.out.print("双向链表: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 反向打印链表内容
    public void printReverseList() {
        Node current = tail;
        System.out.print("反向链表: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}

// 测试双向链表
public class Main {
    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        // 添加节点
        dll.addNode(10);
        dll.addNode(20);
        dll.addNode(30);
        dll.addNode(40);

        // 打印链表
        dll.printList(); // 输出: 双向链表: 10 20 30 40

        // 删除节点
        dll.deleteNode(30);

        // 再次打印链表
        dll.printList(); // 输出: 双向链表: 10 20 40

        // 反向打印链表
        dll.printReverseList(); // 输出: 反向链表: 40 20 10
    }
}

代码说明：

  1. Node 类：定义了双向链表中每个节点的结构，包括数据 (data) 和两个指针 (prev 和 next)。
  2. DoublyLinkedList 类：实现了双向链表的基本操作，包括：
    • addNode：在链表末尾添加节点。
    • deleteNode：删除指定数据的节点。
    • printList：正向打印链表内容。
    • printReverseList：反向打印链表内容。
  3. Main 类：测试双向链表的功能。

通过这个实现，你可以轻松地创建、操作和打印双向链表。

14-简述Java 哈希表基本概念

Java中的哈希表（Hashtable）是一种基于哈希表数据结构实现的集合类，它存储键值对（key-value pairs），并且能够通过键快速查找对应的值。以下是关于Java哈希表的一些基本概念：

  1. 键值对存储
    哈希表中每个元素都是一个键值对，即每个对象都与一个特定的键关联。这意味着你可以通过提供键来检索相应的值。

  2. 哈希函数
    哈希表使用哈希函数将键映射为数组索引。理想情况下，不同的键应该映射到不同的索引位置，但实际上可能会出现多个键映射到相同位置的情况，这被称为“冲突”。

  3. 处理冲突
    当两个或更多的键被分配到了同一个索引时，就需要某种策略来解决这种冲突。常见的方法包括链地址法（分离链接法）和开放寻址法等。在Java的Hashtable以及HashMap中，采用的是链地址法，也就是在发生冲突时，在同一个位置上形成一个链表或红黑树（当链表长度超过一定阈值时转换为红黑树，以提高查找效率）。

  4. 线程安全
    Hashtable是线程同步的，也就是说它是线程安全的。这意味着在同一时间只有一个线程可以修改哈希表的内容，从而避免了并发修改带来的问题。然而，这也意味着它的性能可能不如非同步的同类如HashMap。

  5. 初始容量和加载因子
    创建哈希表时可以指定其初始容量（哈希表中桶的数量）以及加载因子（用来决定何时扩展哈希表大小的比例）。当实际存储元素的数量达到容量乘以加载因子时，哈希表会自动扩大其内部数组的大小以容纳更多元素，这一过程称为再散列（rehashing）。

  6. 遍历方式
    可以通过键集、值集或者条目集的方式遍历哈希表。其中条目集是最常用的方法，因为它允许同时访问键和值。

  7. 迭代器失效
    如果在迭代过程中尝试修改哈希表，则会导致迭代器失效，抛出ConcurrentModificationException异常。对于Hashtable来说，由于它是同步的，所以在多线程环境中进行迭代操作时需要特别小心。

  8. 替代选择
    从JDK 1.2开始，推荐使用HashMap代替Hashtable，因为HashMap具有更好的性能，并且提供了相同的接口。如果确实需要线程安全的实现，可以考虑使用Collections.synchronizedMap()包装HashMap，或者使用ConcurrentHashMap，后者提供了更高的并发性。

以上就是关于Java哈希表的一些基础知识点。希望这些信息对你有所帮助！

15-简述什么是哈希函数？

哈希函数（Hash Function）是一种将任意长度的输入数据映射为固定长度输出的算法。这个输出通常被称为“哈希值”、“散列值”或“消息摘要”。

哈希函数具有以下特点：

  1. 确定性：相同的输入总是产生相同的哈希值。
  2. 固定长度输出：无论输入数据的长度如何，输出的哈希值长度是固定的。
  3. 高效性：计算哈希值的过程应该相对简单且快速。
  4. 雪崩效应：输入数据的微小变化会导致哈希值发生显著变化，这使得预测和逆向工程变得非常困难。
  5. 抗碰撞性：不同输入很难产生相同的哈希值（即碰撞），特别是强抗碰撞性要求找到两个不同的输入产生相同哈希值在计算上是不可行的。

哈希函数广泛应用于计算机科学中的各种场景，例如：

  • 数据检索：如哈希表中用于快速查找数据。
  • 数据完整性验证：通过比较文件的哈希值来确保文件未被篡改。
  • 密码学：用于保护密码存储、数字签名等安全相关应用。
  • 区块链技术：用于构建区块链接结构，保证交易记录的不可篡改性。

常见的哈希函数包括MD5、SHA-1、SHA-256等。需要注意的是，一些较老的哈希函数（如MD5和SHA-1）由于存在已知的安全漏洞，在现代系统中逐渐被更安全的算法取代。

16. 编写Java代码实现哈希表

在Java中，可以通过实现一个简单的哈希表来理解其基本工作原理。以下是一个简化的哈希表实现示例，使用数组作为底层数据结构，并提供基本的插入、查找和删除功能。

代码实现

import java.util.ArrayList;
import java.util.List;

public class SimpleHashTable<K, V> {
    // 定义桶的数量
    private static final int DEFAULT_SIZE = 16;

    // 存储键值对的桶数组
    private List<Entry<K, V>>[] buckets;

    // 构造函数，初始化哈希表
    @SuppressWarnings("unchecked")
    public SimpleHashTable() {
        buckets = new ArrayList[DEFAULT_SIZE];
        for (int i = 0; i < DEFAULT_SIZE; i++) {
            buckets[i] = new ArrayList<>();
        }
    }

    // 插入或更新键值对
    public void put(K key, V value) {
        if (key == null) return;
        int index = getIndex(key);
        List<Entry<K, V>> bucket = buckets[index];
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value; // 更新已有键的值
                return;
            }
        }
        // 如果键不存在，则插入新键值对
        bucket.add(new Entry<>(key, value));
    }

    // 根据键获取值
    public V get(K key) {
        if (key == null) return null;
        int index = getIndex(key);
        List<Entry<K, V>> bucket = buckets[index];
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value; // 找到对应的值
            }
        }
        return null; // 键不存在
    }

    // 删除指定键的键值对
    public void remove(K key) {
        if (key == null) return;
        int index = getIndex(key);
        List<Entry<K, V>> bucket = buckets[index];
        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                bucket.remove(entry); // 删除键值对
                break;
            }
        }
    }

    // 计算哈希索引
    private int getIndex(K key) {
        return Math.abs(key.hashCode()) % buckets.length;
    }

    // 内部类：存储键值对
    private static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 测试哈希表
    public static void main(String[] args) {
        SimpleHashTable<String, Integer> hashTable = new SimpleHashTable<>();
        
        // 插入键值对
        hashTable.put("Alice", 25);
        hashTable.put("Bob", 30);
        hashTable.put("Charlie", 35);

        // 获取值
        System.out.println("Alice's age: " + hashTable.get("Alice")); // 输出 25
        System.out.println("Bob's age: " + hashTable.get("Bob")); // 输出 30

        // 更新值
        hashTable.put("Alice", 26);
        System.out.println("Alice's updated age: " + hashTable.get("Alice")); // 输出 26

        // 删除键值对
        hashTable.remove("Bob");
        System.out.println("Bob's age after removal: " + hashTable.get("Bob")); // 输出 null
    }
}

代码说明

  1. 哈希表结构：

    • 使用 List<Entry<K, V>>[] 数组作为桶（bucket）的存储结构。
    • 每个桶存储一个链表，用于处理哈希冲突（即多个键映射到同一个桶的情况）。

  2. 核心方法：

    • put(K key, V value)：插入或更新键值对。
    • get(K key)：根据键获取对应的值。
    • remove(K key)：删除指定键的键值对。
    • getIndex(K key)：通过哈希函数计算键的索引位置。

  3. 哈希函数：

    • 使用 Math.abs(key.hashCode()) % buckets.length 计算键的哈希值并映射到桶数组的索引位置。

  4. 冲突解决：

    • 当多个键映射到同一个桶时，使用链地址法（将键值对存储在链表中）解决冲突。

  5. 测试部分：

    • 创建了一个简单的哈希表实例，并演示了插入、获取、更新和删除操作。

可扩展性

  • 动态扩容

17. 简述Java树的基本概念和组成？

在Java中，树是一种非线性的数据结构，它由节点组成，这些节点通过边连接。树的结构类似于自然界中的树，有根、分支和叶子等概念，用于表示层次化的数据结构。

基本概念

  1. 节点（Node）：树的基本组成部分。每个节点包含一个值或一组数据以及指向其他节点的链接。
  2. 根节点（Root Node）：树的最顶层节点，没有父节点。
  3. 子节点（Child Node）：除了根节点以外的节点可以有零个或多个子节点。
  4. 父节点（Parent Node）：与子节点相对，每个子节点都有一个父节点，根节点除外。
  5. 兄弟节点（Sibling Nodes）：具有相同父节点的节点互为兄弟节点。
  6. 叶节点（Leaf Node）：没有子节点的节点，也称为终端节点。
  7. 路径（Path）：从一个节点到另一个节点所经过的节点序列。
  8. 深度（Depth）：指某个节点在其树中的层数，根节点的深度为0。
  9. 高度（Height）：对于给定节点，其子树中最长路径上节点的数量；对于整个树而言，是根到最远叶节点的最长路径上的节点数减一。
  10. 森林（Forest）：若干棵不相交的树组成的集合。

树的组成

  • 节点结构：通常包括数据域（存储实际数据）和指针域（指向子节点）。例如，在二叉树中，每个节点有两个指针分别指向左子节点和右子节点。
  • 遍历方法：为了访问树的所有元素，提供了多种遍历方式，如前序遍历（Pre-order）、中序遍历（In-order）、后序遍历（Post-order）及层次遍历（Level-order）。

Java实现示例

在Java中创建树时，可以通过定义一个TreeNode类来表示单个节点，并使用递归或其他迭代算法来构建和操作树结构。下面是一个简单的二叉树节点类的例子：

class TreeNode {
    int value; // 节点值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点

    public TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

然后可以根据具体需求进一步扩展此基础类以支持更多功能，比如插入新节点、删除节点、查找特定值等操作。此外，还可以根据应用场景选择不同的树类型，如二叉搜索树（BST）、平衡树（AVL树、红黑树）等。

18-简述什么是二叉树

二叉树是一种常见的树形数据结构，其特点是每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树具有以下基本特性：

  1. 节点结构：每个节点包含三个部分：节点的数据（值）、指向左子节点的引用、指向右子节点的引用。
  2. 根节点：二叉树的最顶端节点被称为根节点。
  3. 叶子节点：没有子节点的节点被称为叶子节点或终端节点。
  4. 深度与高度：
    • 节点的深度是指从根节点到该节点的路径长度。
    • 节点的高度是指从该节点到最远叶子节点的路径长度。
    • 树的高度是指树中节点的最大高度。
  5. 满二叉树：除最后一层外，每一层上的所有节点都有两个子节点的二叉树。
  6. 完全二叉树：除最后一层外，每一层都被完全填充，并且最后一层的节点都靠左对齐的二叉树。

二叉树有多种遍历方式，包括前序遍历、中序遍历、后序遍历和层次遍历等，这些遍历方法在不同的应用场景中有各自的用途。此外，二叉树还衍生出许多特殊类型的树，如二叉搜索树（BST）、平衡二叉树（AVL树）和红黑树等，在实际应用中广泛用于实现高效的数据存储、检索和排序操作。

19- 简述什么是满二叉树

满二叉树（Full Binary Tree）是二叉树的一种特殊形式，其特点是：

  1. 每个节点要么没有子节点（即为叶子节点），要么有两个子节点。换句话说，满二叉树中的每个非叶子节点都必须有两个子节点。
  2. 所有叶子节点都在同一层，并且该层是树的最后一层。

特点：

  • 满二叉树的高度为 h 时，总节点数为 2^h - 1，其中 h 是从根节点开始的层数（根节点位于第 0 层）。
  • 满二叉树的第 i 层有 2^i 个节点（i = 0, 1, 2, ..., h-1）。
  • 满二叉树的叶子节点数等于非叶子节点数加 1。

示例：

一个高度为 3 的满二叉树如下所示：

        A
       / \
      B   C
     / \ / \
    D  E F  G

在这个例子中，每个非叶子节点都有两个子节点，且所有叶子节点（D、E、F、G）都在同一层。

区别：

  • 满二叉树与完全二叉树不同： 完全二叉树允许最后一层的节点不满，但必须从左到右填充。
  • 满二叉树与完美二叉树（Perfect Binary Tree）不同： 完美二叉树不仅要求每个非叶子节点有两个子节点，还要求所有叶子节点都在最后一层，并且左右子树结构完全对称。

希望这个解释对你理解满二叉树有所帮助！

20-简述什么是完全二叉树？

完全二叉树（Complete Binary Tree）是一种特殊的二叉树结构，它具有以下特点：

  1. 除了最后一层外，其他各层的节点数都达到最大
    也就是说，从根节点开始，每一层的节点数都是2的幂次方，直到倒数第二层为止。

  2. 最后一层的节点都尽可能靠左排列
    如果最后一层的节点不是满的，那么这些节点必须从左到右连续分布，不能有空缺。换句话说，不存在某个节点的右子节点存在而左子节点不存在的情况。

  3. 叶子节点只能出现在最底层或次底层
    完全二叉树的叶子节点（没有子节点的节点）只可能出现在最底层和次底层，并且最底层的叶子节点都靠左对齐。

示例：

  • 一个高度为3的完全二叉树可能有7个节点（满二叉树），或者8到14个节点。
  • 如果一个完全二叉树有10个节点，那么它的结构应该是：
    第一层1个节点，第二层2个节点，第三层4个节点，第四层3个节点（且这3个节点靠左排列）。

完全二叉树的特点：

  • 高效存储：完全二叉树可以使用数组来高效地存储，因为每个节点的位置可以通过简单的数学公式计算得出。例如，对于数组中的第i个元素（假设根节点在位置1），其左子节点在位置2i，右子节点在位置2i+1。

  • 常用于堆结构：完全二叉树常用于实现堆（Heap）数据结构，如最大堆和最小堆。

总结来说，完全二叉树是一种接近满二叉树的结构，它保证了节点的紧凑性和层次结构的完整性，因此在很多算法和数据结构中都有广泛的应用。

21. 简述二叉树的存储方式？

二叉树是一种常见的数据结构，其存储方式通常有两种：顺序存储和链式存储。以下是两种存储方式的简要说明：

1. 顺序存储

  • 定义：使用数组来存储二叉树中的节点。
  • 特点：
    • 按照二叉树的层序遍历顺序将节点存入数组中。
    • 对于完全二叉树或满二叉树，顺序存储非常高效，因为可以利用父子节点之间的下标关系快速定位。
    • 父节点下标为 i，则左子节点下标为 2*i+1，右子节点下标为 2*i+2。
    • 如果二叉树不是完全二叉树，则需要在数组中留出空位（用特殊值表示），这会导致空间浪费。

2. 链式存储

  • 定义：通过指针（引用）的方式将二叉树的节点连接起来。
  • 特点：
    • 每个节点包含三个部分：数据域、左孩子指针和右孩子指针。
    • 不依赖于二叉树的形状，适合任意形态的二叉树。
    • 空间利用率较高，不会出现像顺序存储那样的大量空位问题。
    • 实现灵活，但查找父节点时需要额外操作（如引入三叉链表结构，增加一个指向父节点的指针）。

总结

  • 顺序存储适用于完全二叉树或满二叉树，简单高效但可能浪费空间。
  • 链式存储适用于任意形态的二叉树，灵活但需要额外的指针空间。

具体选择哪种存储方式，取决于二叉树的实际应用场景和形态特征。

22 - 简述树的三种遍历顺序

树的三种常见的遍历顺序主要应用于二叉树，分别是：

  1. 前序遍历（Pre-order Traversal）：

    • 访问顺序为：根节点 → 左子树 → 右子树。
    • 具体过程是先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。

  2. 中序遍历（In-order Traversal）：

    • 访问顺序为：左子树 → 根节点 → 右子树。
    • 具体过程是先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。对于二叉搜索树来说，中序遍历的结果是按节点值从小到大排列的。

  3. 后序遍历（Post-order Traversal）：

    • 访问顺序为：左子树 → 右子树 → 根节点。
    • 具体过程是先递归地对左子树进行后序遍历，再递归地对右子树进行后序遍历，最后访问根节点。

这三种遍历方式都是深度优先搜索（DFS）的具体形式，每种遍历方式适用于不同的场景和需求。例如，前序遍历常用于复制树结构，中序遍历适用于遍历有序数据（如二叉搜索树），而后序遍历则常用于删除树节点等操作。

23-编写Java代码实现二叉树的构建和遍历

下面是一个简单的Java代码示例，用于构建二叉树并实现三种常见的遍历方法：前序遍历、中序遍历和后序遍历。

1. 定义二叉树节点类 TreeNode

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    // 构造函数
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

2. 定义二叉树类 BinaryTree

class BinaryTree {
    TreeNode root;
    
    // 构造函数
    BinaryTree() {
        root = null;
    }
    
    // 前序遍历：根 -> 左 -> 右
    void preOrder(TreeNode node) {
        if (node == null) return;
        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
    
    // 中序遍历：左 -> 根 -> 右
    void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }
    
    // 后序遍历：左 -> 右 -> 根
    void postOrder(TreeNode node) {
        if (node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }
}

3. 主程序：构建二叉树并进行遍历

public class Main {
    public static void main(String[] args) {
        // 创建二叉树对象
        BinaryTree tree = new BinaryTree();
        
        // 手动构建一个简单的二叉树
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);
        tree.root.right.left = new TreeNode(6);
        tree.root.right.right = new TreeNode(7);
        
        // 输出二叉树的结构
        System.out.println("前序遍历: ");
        tree.preOrder(tree.root);
        
        System.out.println("\n中序遍历: ");
        tree.inOrder(tree.root);
        
        System.out.println("\n后序遍历: ");
        tree.postOrder(tree.root);
    }
}

4. 运行结果

假设我们构建了如下的二叉树：

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

运行上述代码后，输出结果如下：

前序遍历:
1 2 4 5 3 6 7

中序遍历:
4 2 5 1 6 3 7

后序遍历:
4 5 2 6 7 3 1

5. 说明

  • 前序遍历：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。
  • 中序遍历：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。
  • 后序遍历：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

你可以根据需要扩展这个例子，例如添加更多功能（如插入节点、删除节点等），或者使用更复杂的数据结构来构建二叉树。

24-简述什么是平衡二叉树（AVL Tree）？

平衡二叉树（AVL Tree）是一种特殊的二叉搜索树，它具有自我平衡的特性。AVL树得名于其发明者G.M. Adelson-Velsky和E.M. Landis，他们在1962年发表了相关论文。

主要特点：

  1. 定义：
    AVL树是一棵二叉搜索树，其中每个节点的左右子树的高度差最多为1。这种高度差被称为平衡因子，取值范围为{-1, 0, 1}。

  2. 平衡因子：
    每个节点的平衡因子等于其左子树的高度减去右子树的高度。如果平衡因子超出这个范围（即超过1或低于-1），则需要通过旋转操作来重新平衡树。

  3. 旋转操作：
    当插入或删除节点导致树失去平衡时，AVL树会通过以下四种旋转操作之一来恢复平衡：

    • 单左旋（LL旋转）：当新插入的节点在左子树的左侧时使用。
    • 单右旋（RR旋转）：当新插入的节点在右子树的右侧时使用。
    • 双旋（LR旋转）：先对左子树进行右旋，再对根节点进行左旋，适用于新节点插入在左子树的右侧。
    • 双旋（RL旋转）：先对右子树进行左旋，再对根节点进行右旋，适用于新节点插入在右子树的左侧。

  4. 查找、插入、删除的时间复杂度：
    由于AVL树始终保持接近完全平衡的状态，因此其查找、插入和删除操作的时间复杂度均为O(log n)，其中n是树中节点的数量。

总结：

AVL树通过严格的平衡条件确保了树的高度始终保持在O(log n)级别，从而保证了高效的查找、插入和删除操作。然而，频繁的旋转操作使得AVL树在某些场景下的性能可能不如其他自平衡树（如红黑树）高效，尤其是在频繁插入和删除的情况下。

25-简述什么是B-tree、B+tree多叉树？

B-tree（B树）

定义：
B-tree 是一种自平衡的多叉搜索树，常用于数据库和文件系统中，以支持快速的查找、插入和删除操作。它通过将数据分散在多个节点上，减少了磁盘I/O次数，提高了效率。

特点：

  1. 节点结构： 每个节点可以包含多个键值和子节点指针。根节点至少有2个子节点，其他非叶子节点至少有 (lceil m/2 ceil - 1) 个键（其中 (m) 是阶数），最多可以有 (m-1) 个键。
  2. 平衡性： 所有叶子节点都位于同一层，确保了树的高度较低，从而减少查找深度。
  3. 高效查找： 在每个节点内进行二分查找，时间复杂度为 O(log n)。
  4. 插入与删除： 当插入或删除导致节点过满或不满时，会通过分裂或合并节点来保持树的平衡。

B+tree（B+树）

定义：
B+tree 是 B-tree 的一种变体，主要用于数据库和文件系统的索引结构。与 B-tree 相比，B+tree 在存储和检索方面有一些优化，特别是对范围查询更为友好。

特点：

  1. 节点结构：
    • 内部节点： 只包含键值和子节点指针，不存储实际数据。
    • 叶子节点： 包含键值和指向实际数据的指针，并且所有的叶子节点通过指针链接在一起形成一个链表。
  2. 叶子节点链接： 所有叶子节点之间通过双向链表连接，便于范围查询。
  3. 高度平衡： 所有叶子节点位于同一层，确保了树的高度较低。
  4. 高效查找： 同样在每个节点内进行二分查找，时间复杂度为 O(log n)。
  5. 插入与删除： 与 B-tree 类似，通过分裂或合并节点来保持树的平衡，但 B+tree 的叶子节点分裂和合并规则略有不同。

B-tree 和 B+tree 的主要区别：

  1. 数据存储位置：

    • B-tree： 数据可以存储在内部节点和叶子节点中。
    • B+tree： 数据只存储在叶子节点中，内部节点仅用于索引。

  2. 范围查询：

    • B-tree： 由于数据分布在所有节点中，范围查询需要多次回溯。
    • B+tree： 由于叶子节点通过链表连接，范围查询更加高效。

  3. 缓存性能：

    • B+tree： 叶子节点紧凑存储，减少了磁盘I/O次数，更适合外存访问。

总的来说，B-tree 和 B+tree 都是高效的多叉搜索树，但在具体应用场景中各有优势。例如，B+tree 更适合范围查询和顺序扫描，而 B-tree 在某些情况下可能更适合点查询。

26-简述什么是红黑树？

红黑树（Red-Black Tree）是一种自平衡二叉查找树（Binary Search Tree, BST），它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，从而保证了树的近似平衡。

红黑树具有以下特性：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点总是黑色。
  3. 所有叶子节点（NIL节点，空节点）都是黑色。（这里需要注意的是，在实现中通常用一个哨兵节点代替实际的NULL值）
  4. 如果一个节点是红色，则它的两个子节点都是黑色。（即不能有两个连续的红色节点）
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质共同作用以保证红黑树的高度大致为O(log n)，其中n是节点的数量。因此，基本动态集合操作（如最小值、最大值、后继、前驱、插入和删除等）的时间复杂度都保持在O(log n)。

红黑树被广泛应用于各种编程语言的标准库中，例如C++ STL中的map和set容器，以及Java中的TreeMap和TreeSet类。

27-解释AVL树和红黑树的区别？

AVL树和红黑树都是自平衡二叉搜索树（Self-Balancing Binary Search Tree），但它们在平衡策略、插入/删除操作的复杂度以及应用场景等方面存在显著区别。以下是它们的主要差异点：

1. 平衡策略

  • AVL树:

    • AVL树通过严格限制左右子树的高度差来维持平衡，要求任意节点的左右子树高度差绝对值不超过1。
    • 每次插入或删除节点后，可能会触发旋转操作（单旋转或双旋转）以恢复平衡。

  • 红黑树:

    • 红黑树使用颜色标记（红色或黑色）和一组规则来保证近似平衡：
      1. 每个节点是红色或黑色。
      2. 根节点必须是黑色。
      3. 所有叶子节点（NIL节点）是黑色。
      4. 如果一个节点是红色，则它的两个子节点必须是黑色（即不能连续出现红色节点）。
      5. 从任一节点到其每个叶子的所有路径上，包含相同数量的黑色节点。
    • 红黑树不要求严格的平衡，允许一定程度的不平衡，但整体保持近似平衡。

2. 平衡代价

  • AVL树:

    • 因为需要严格维持高度平衡，每次插入或删除操作后可能需要进行多次旋转以恢复平衡。
    • 插入和删除的时间复杂度均为 ( O(\log n) )，但常数因子较大。

  • 红黑树:

    • 平衡条件较宽松，因此插入或删除操作所需的调整较少。
    • 插入和删除的时间复杂度也为 ( O(\log n) )，但由于调整次数较少，实际性能通常优于AVL树。

3. 查询效率

  • AVL树:

    • 由于高度严格平衡，AVL树的高度始终接近 ( \log_2(n+1) )，查询效率较高。
    • 适合对查询性能要求极高的场景。

  • 红黑树:

    • 虽然红黑树不完全平衡，但其高度不会超过 ( 2\log_2(n+1) )，查询效率仍然很高。
    • 在大多数情况下，查询性能与AVL树相差不大。

4. 应用场景

  • AVL树:

    • 更适合需要频繁查询而插入/删除操作较少的场景。
    • 例如：数据库索引、缓存系统等。

  • 红黑树:

    • 更适合插入/删除操作频繁的场景，因为其调整开销较小。
    • 例如：C++ STL中的 std::map 和 std::set 通常基于红黑树实现。

5. 空间复杂度

  • AVL树:

    • 不需要额外的颜色信息，空间利用率略高。

  • 红黑树:

    • 每个节点需要存储额外的颜色信息（1位），空间开销略大。

总结表格

特性AVL树红黑树
平衡策略高度严格平衡近似平衡，允许一定不平衡
插入/删除代价较高（可能多次旋转）较低（调整次数少）
查询效率高较高
适用场景查询为主，修改较少修改频繁
空间复杂度不需要额外颜色信息每个节点需要1位颜色信息

结论

如果应用中查询操作远多于插入和删除操作，可以选择AVL树；如果插入和删除操作较为频繁，则红黑树更为合适。两者各有优劣，选择时应根据具体需求权衡。

28. 综合简述 B 树和 B+ 树的区别

B 树（B-tree）和 B+ 树（B+-tree）是两种广泛应用于数据库和文件系统中的平衡树数据结构，它们用于高效地存储和检索大量有序数据。尽管这两种树在某些方面有相似之处，但它们之间也存在一些关键区别。以下是 B 树和 B+ 树的主要区别：

1. 节点的存储结构

  • B 树：每个节点既可以存储键值（key），也可以存储与键关联的数据（或指向下一层的数据）。这意味着 B 树的内部节点和叶子节点都可以存储数据。
  • B+ 树：只有叶子节点存储实际的数据记录，而内部节点只存储键值，用于引导查找。所有数据都集中在叶子节点中。

2. 叶子节点的链接

  • B 树：叶子节点之间没有直接的链接关系，查找时必须从根节点开始逐层遍历。
  • B+ 树：所有的叶子节点通过双向链表相互链接，这使得范围查询非常高效，可以在找到第一个匹配的叶子节点后，快速遍历后续的叶子节点。

3. 查找效率

  • B 树：每次查找、插入或删除操作的时间复杂度为 O(logₘN)，其中 m 是树的阶数，N 是元素个数。由于内部节点也存储数据，因此查找某个键时可能会在非叶子节点上命中。
  • B+ 树：查找的时间复杂度同样是 O(logₘN)，但由于所有数据都在叶子节点，查找过程中不会在非叶子节点上命中数据。对于范围查询，B+ 树比 B 树更高效，因为可以利用叶子节点之间的链表快速遍历。

4. 插入和删除的处理

  • B 树：插入和删除操作可能导致内部节点分裂或合并，影响树的高度，但由于内部节点存储数据，分裂或合并时需要调整更多的数据。
  • B+ 树：插入和删除只会影响叶子节点，内部节点只存储键值，因此分裂或合并的影响较小，且叶子节点之间的链表结构使得维护更加简单。

5. 空间利用率

  • B 树：由于内部节点和叶子节点都存储数据，空间利用率相对较低，尤其是在内部节点中存储了大量数据的情况下。
  • B+ 树：所有数据集中在叶子节点中，内部节点只存储键值，因此空间利用率更高，且叶子节点通常可以容纳更多的键值。

6. 适用场景

  • B 树：适用于需要频繁进行点查询（即查找单个键）的场景，因为它的内部节点也存储数据，可能在非叶子节点上命中。
  • B+ 树：更适合范围查询和顺序扫描，因为在 B+ 树中，所有数据都在叶子节点，并且叶子节点之间有链表连接，便于快速遍历。

总结：

  • B 树 更适合点查询，因为它可以在非叶子节点上命中数据。
  • B+ 树 更适合范围查询和顺序扫描，因为所有数据集中在叶子节点，并且叶子节点之间有链表连接，便于快速遍历。

在实际应用中，B+ 树更为常见，尤其是在数据库索引和文件系统中，因为它的设计更好地支持范围查询和顺序访问。

29-简述链表和数组的区别

链表和数组是两种常见的线性数据结构，它们在存储方式、访问效率和操作灵活性等方面存在显著差异。以下是链表和数组的主要区别：

1. 存储方式

  • 数组：数组是一块连续的内存空间，所有元素按顺序依次排列。数组的大小在创建时通常是固定的（动态数组除外），且每个元素的类型相同。
  • 链表：链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针（单向链表）或前后节点的指针（双向链表）。链表的节点可以分散在不同的内存位置，节点之间通过指针连接。

2. 访问效率

  • 数组：由于数组是连续存储的，可以通过索引直接访问任意元素，时间复杂度为 O(1)。
  • 链表：链表不能通过索引直接访问元素，必须从头节点开始逐个遍历，直到找到目标节点，因此查找的时间复杂度为 O(n)，n 是链表的长度。

3. 插入和删除操作

  • 数组：在数组中插入或删除元素（特别是在中间位置）需要移动大量元素以保持连续性，时间复杂度为 O(n)。
  • 链表：在链表中插入或删除节点只需要修改相关节点的指针，不需要移动其他节点，时间复杂度为 O(1)（如果已经找到了要操作的节点）。但在链表中找到要操作的节点仍然需要 O(n) 的时间。

4. 内存使用

  • 数组：数组的空间是预先分配好的，可能会导致内存浪费（如果实际使用的元素较少），或者在需要更多空间时无法扩展（固定大小的数组）。
  • 链表：链表的节点可以在运行时动态分配和释放，内存利用率较高，适合处理不确定数量的元素。但由于每个节点都包含额外的指针，链表会占用更多的内存。

5. 应用场景

  • 数组：适用于频繁进行随机访问的场景，如矩阵运算、图像处理等。
  • 链表：适用于频繁插入和删除操作的场景，如队列、栈等。

总结

  • 数组：优点是随机访问快，缺点是插入删除效率低，内存固定。
  • 链表：优点是插入删除快，缺点是随机访问慢，内存开销较大。

根据具体的应用场景选择合适的数据结构可以提高程序的效率。

30. 编写Java代码栈实现Push、pop以及max，要求时间复杂度为O（1）

要在Java中实现一个栈，使其支持push、pop和max操作，并且每个操作的时间复杂度为O(1)，我们可以使用两个栈：一个用于存储所有元素，另一个用于存储当前的最大值。

具体来说：

  • 主栈（mainStack）用于存储所有元素。
  • 辅助栈（maxStack）用于存储每次操作后的最大值。

每当有新元素入栈时，如果它比当前的最大值大或相等，则将该元素也压入辅助栈；每当有元素出栈时，如果它等于当前的最大值，则也将辅助栈的栈顶元素弹出。

以下是具体的实现代码：

import java.util.Stack;

public class MaxStack {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> maxStack = new Stack<>();
    
    // Push element x onto stack.
    public void push(int x) {
        mainStack.push(x);
        if (maxStack.isEmpty() || x >= maxStack.peek()) {
            maxStack.push(x);
        }
    }
    
    // Removes the element on top of the stack.
    public void pop() {
        if (!mainStack.isEmpty()) {
            int top = mainStack.pop();
            if (top == maxStack.peek()) {
                maxStack.pop();
            }
        }
    }
    
    // Get the top element.
    public int top() {
        if (!mainStack.isEmpty()) {
            return mainStack.peek();
        }
        throw new RuntimeException("Stack is empty");
    }
    
    // Retrieve the maximum element in the stack.
    public int getMax() {
        if (!maxStack.isEmpty()) {
            return maxStack.peek();
        }
        throw new RuntimeException("Stack is empty");
    }
    
    public static void main(String[] args) {
        MaxStack maxStack = new MaxStack();
        maxStack.push(2);
        maxStack.push(1);
        System.out.println(maxStack.getMax()); // Output: 2
        maxStack.push(3);
        System.out.println(maxStack.getMax()); // Output: 3
        maxStack.pop();
        System.out.println(maxStack.getMax()); // Output: 2
        maxStack.pop();
        System.out.println(maxStack.getMax()); // Output: 2
    }
}

解释：

  1. Push操作：当新元素入栈时，检查辅助栈是否为空或新元素是否大于等于辅助栈的栈顶元素。如果是，则将新元素也压入辅助栈。
  2. Pop操作：当元素出栈时，检查出栈元素是否等于辅助栈的栈顶元素。如果是，则也将辅助栈的栈顶元素弹出。
  3. GetMax操作：直接返回辅助栈的栈顶元素，即当前的最大值。

通过这种方式，我们可以在O(1)时间内完成push、pop和getMax操作。

31-编写Java代码实现合并链表

在 Java 中，合并两个有序链表的常见方法是使用递归或迭代。下面我将展示如何编写一个非递归（迭代）版本的代码来合并两个升序排列的链表，并返回一个新的升序链表。

1. 定义链表节点类

首先，我们需要定义一个链表节点类 ListNode，它包含两个属性：val 表示节点的值，next 表示指向下一个节点的引用。

class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
    
    // 构造函数，用于创建带有下一个节点的节点
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

2. 合并两个有序链表的方法

接下来，我们编写一个方法 mergeTwoLists 来合并两个升序链表。这个方法会遍历两个链表，并按顺序将较小的节点添加到结果链表中。

public class MergeLinkedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点，简化边界条件处理
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // 当两个链表都不为空时，比较它们的头节点
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // 如果其中一个链表还有剩余节点，直接连接到结果链表
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }
        
        // 返回合并后的链表，跳过虚拟头节点
        return dummy.next;
    }

    // 辅助方法：打印链表内容
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }

    // 测试代码
    public static void main(String[] args) {
        // 创建两个测试链表
        ListNode l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode l2 = new ListNode(2, new ListNode(4, new ListNode(6)));
        
        // 打印原始链表
        System.out.print("链表1: ");
        printList(l1);
        System.out.print("链表2: ");
        printList(l2);
        
        // 合并链表
        ListNode mergedList = mergeTwoLists(l1, l2);
        
        // 打印合并后的链表
        System.out.print("合并后的链表: ");
        printList(mergedList);
    }
}

代码说明：

  1. ListNode 类：这是链表节点的定义，每个节点包含一个整数值和指向下一个节点的引用。
  2. mergeTwoLists 方法：该方法接受两个链表 l1 和 l2，并返回一个新的合并后的链表。它使用了一个虚拟头节点 dummy 来简化操作，避免处理空链表的情况。
  3. printList 方法：这是一个辅助方法，用于打印链表的内容。
  4. main 方法：用于测试合并功能，创建了两个链表并调用 mergeTwoLists 方法进行合并，最后打印出合并后的结果。

输出结果：

假设输入的两个链表分别是 1 -> 3 -> 5 和 2 -> 4 -> 6，程序的输出将是：

链表1: 1 -> 3 -> 5 -> null
链表2: 2 -> 4 -> 6 -> null
合并后的链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

这段代码可以很好地处理两个有序链表的合并问题。你可以根据需要调整链表的输入数据进行测试。

32-简述如何实现旋转词

/**

  • 参数字符串是否是当前字符串的旋转词
  • 旋转词指的是各个字符的相对顺序不变，但是位置不同的字符串
  • 比如 123, 231, 312
  • 最优解算法为 O(n)
  • 算法：
  • 1 ）比较长度是否相同
  • 2 ）如果相同，生成 str1+str1 的大字符串
  • 3 ）用 KMP 算法判断大字符串中是否包含 str2
  • @param str
  • @return
    */
public boolean isRotationWord(MyString str) {
    if (value.length != str.length()) {
        return false;
    }
    MyString newStr = this.concat(this);
    return newStr.indexOf(str) != -1;
}

33-简述如何实现单词间逆序

/**

  • 在单词间做一个逆序，但单词内不做逆序
  • 示例：
  • "dog loves pig" -> "pig loves dog"
  • 算法：
  • 1 ）将整个字符串逆序
  • 2 ）对每个单词再做逆序
  • @return
    */
public MyString reverseBetweenWords() {
    // 拷贝一份
    char[] chars = new char[this.value.length];
    System.arraycopy(value, 0, chars, 0, value.length);
    
    // 将整个字符数组逆序
    reverse(chars, 0, chars.length - 1);
    
    int low = 0;
    for (int i = 0; i < chars.length; i++) {
        if (Character.isWhitespace(chars[i])) {
            reverse(chars, low, i - 1);  // 对每个单词逆序
            low = i + 1;
        } else if (i == chars.length - 1) {
            reverse(chars, low, chars.length - 1);
        }
    }
    return new MyString(chars);
}

public static void reverse(char[] chars, int low, int high) {
    assert low <= high;
    int length = high - low + 1;
    char temp;
    for (int i = 0; i < length / 2; i++) {
        temp = chars[i + low];
        chars[i + low] = chars[high - i];
        chars[high - i] = temp;
    }
}

34-简述如何实现字符串循环左移

/**
* 比如 "ABCDE", n=3 -> "DEABC"
* 时间复杂度为 O(n)，空间复杂度为 O(1)
* 做三次逆序：
* 1) [0, len - 1] 逆序（前 n 个）
* 2) [len, N - 1] 逆序（剩下的）
* 3) [0, N - 1] 逆序（全部）
*
* @param len
* @return
*/
public MyString leftShift(int len) {
    char[] chars = new char[this.value.length];
    System.arraycopy(value, 0, chars, 0, value.length);
    reverse(chars, 0, len - 1);
    reverse(chars, len, chars.length - 1);
    reverse(chars, 0, chars.length - 1);
    return new MyString(chars);
}

35-简述如何Java实现字符串数组拼接为最小字符串

/**
* 找到一种拼接顺序，使得拼接后的整个字符串的字典序最小
* 最优复杂度为 O(nlogn)
* 实质上是一个排序
* 注意不能直接按字典序排序，比如 ["ba","b"] -> ["b","ba"] "bab" < "bba"
* 要这样排序：
* 如果 str1+str2 < str2+str1 ，那么 str1 < str2
* 
* @param arr
* @return
*/
public static MyString concatArrayToMinString(MyString[] arr) {
    Comparator<MyString> comp = new Comparator<MyString>() {
        @Override
        public int compare(MyString o1, MyString o2) {
            return o1.concat(o2).compareTo(o2.concat(o1));
        }
    };
    Arrays.sort(arr, comp);
    StringBuilder sb = new StringBuilder();
    for(MyString s : arr) {
        sb.append(s.value);
    }
    return new MyString(sb.toString());
}

36 - 简述如何编程变形词？

/**
 * 变形词：两个字符串，如果出现的字符是一样的并且每个字符出现次数一样，则返回 true；
 * 否则返回 false。
 * 比如 "abc" "bca"
 * 哈希表，字符统计
 * 可以使用定长数组来取代哈希表，时间复杂度为 O(n)，空间复杂度为 O(n)。
 * char -> 使用长度为 256 的数组
 * 
 * @param str
 * @return
 */

public boolean isTransferWord(MyString str) {
    Map<Character, Integer> s1 = new HashMap<>();
    for (char c : this.value) {
        if (s1.get(c) == null) {
            s1.put(c, 1);
        } else {
            s1.put(c, s1.get(c) + 1);
        }
    }
    
    Map<Character, Integer> s2 = new HashMap<>();
    for (char c : str.value) {
        if (s2.get(c) == null) {
            s2.put(c, 1);
        } else {
            s2.put(c, s2.get(c) + 1);
        }
    }
    
    if (s1.size() != s2.size()) {
        return false;
    }
    
    for (Map.Entry<Character, Integer> entry : s1.entrySet()) {
        if (!entry.getValue().equals(s2.get(entry.getKey()))) {
            return false;
        }
    }
    
    return true;
}

37-简述如何实现二叉树非递归先中后序遍历？

不管是递归还是非递归，时间复杂度均为 O(N)，空间复杂度均为 O(H)，H 为高度。

非递归 先序遍历

private void noRecPreOrder(TreeNode<E> curr) {
    Stack<TreeNode<E>> stack = new Stack<>();
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            System.out.print(curr.val + " ");
            stack.push(curr);
            curr = curr.left; // 访问左子树
        }
        if (!stack.isEmpty()) {
            curr = stack.pop();
            curr = curr.right; // 访问右子树
        }
    }
    System.out.println();
}

非递归 中序遍历

private void noRecInOrder(TreeNode<E> curr) {
    Stack<TreeNode<E>> stack = new Stack<>();
    // subTree 不为空，则表示存在，需要进行访问；栈不为空表示没有全部遍历完。只要当前没有遍历完或整体没有遍历完，都进入循环体
    // 如果 subTree 不为空，则先访问其左子树，在此之前需要将结点入栈（每次访问左子树之前都将当前结点入栈）
    // 如果为空，表示左子树不存在，那么出栈，访问右子树，重新进入循环体
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            // while 表示不断地访问其左子树，直至达到左子树的最底端
            stack.push(curr);
            curr = curr.left; // 访问左子树
        }
        if (!stack.isEmpty()) {
            curr = stack.pop();
            System.out.print(curr.val + " "); // 访问数据域
            curr = curr.right; // 访问右子树
        }
    }
    System.out.println();
}

38 - 简述如何实现二叉树层序遍历？

public void levelOrder() {
    Queue<TreeNode<E>> queue = new ArrayDeque<>();
    queue.add(root);
    TreeNode<E> node;
    
    while (!queue.isEmpty()) {
        node = queue.poll();
        System.out.print(node.val + " ");
        
        if (node.left != null) {
            queue.add(node.left);
        }
        
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    
    System.out.println();
}

39-简述如何实现二叉树换行层序遍历

/**
 * 层序遍历，并且打印一层就换一行
 * last 指向当前行的最后一个结点，如果访问完当前节点，并且将左右孩子入队后，
 * 发现自己就是 last ，那么将 last 更新为 nextLast （下一行的最后一个结点），并且换行。
 * nextLast 在孩子入队时更新， last 在当前节点遍历完后有可能会被更新
 */
public void levelOrderWithLine() {
    Queue<TreeNode<E>> queue = new ArrayDeque<>();
    TreeNode<E> node = null;
    // 当前行最右节点
    TreeNode<E> last = root;
    // 下一行最右节点
    TreeNode<E> nextLast = null;
    queue.add(root);
    
    while (!queue.isEmpty()) {
        node = queue.poll();
        System.out.print(node.data + " ");
        
        if (node.left != null) {
            queue.add(node.left);
            nextLast = node.left;
        }
        
        if (node.right != null) {
            queue.add(node.right);
            nextLast = node.right;
        }
        
        // 自己就是当前行的最后一个节点，则更新 last 为下一行的最后一个节点，并且换行
        if (node == last && nextLast != null) {
            last = nextLast;
            nextLast = null;
            System.out.println();
        }
    }
}

40-简述实现二叉树层序遍历至二维数组

public List<List<E>> levelOrderToListWithLine() {
    List<List<E>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    Queue<TreeNode<E>> queue = new ArrayDeque<>();
    TreeNode<E> node = null;
    // 当前行最右节点
    TreeNode<E> last = root;
    // 下一行最右节点
    TreeNode<E> nextLast = null;
    queue.add(root);
    int level = 0;

    while (!queue.isEmpty()) {
        node = queue.poll();
        result.get(level).add(node.data);

        if (node.left != null) {
            queue.add(node.left);
            nextLast = node.left;
        }
        if (node.right != null) {
            queue.add(node.right);
            nextLast = node.right;
        }

        // 自己就是当前行的最后一个节点，则更新 last 为下一行的最后一个节点，并且换行
        if (node == last && nextLast != null) {
            last = nextLast;
            nextLast = null;
            level++;
            result.add(new ArrayList());
        }
    }
    return result;
}

41-简述之字形打印二叉树

/**
 * 类似于层序遍历，但是队列的入队、出队规则不同
 * @return
 */
public List<List<E>> printZ() {
    TreeNode<E> curr;
    Deque<TreeNode<E>> queue = new ArrayDeque<>();
    List<List<E>> result = new ArrayList<>();
    queue.add(root);
    int depth = 0;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<E> levelResult = new ArrayList<>();
        // 一层进行遍历,queue 的长度即为该层节点个数
        for (int i = 0; i < levelSize; i++) {
            if (depth % 2 == 0) {
                // 如果是偶数层，那么从队尾取出节点，先左后右，加入到队头
                curr = queue.pollLast();
                if (curr.left != null) {
                    queue.offerFirst(curr.left);
                }
                if (curr.right != null) {
                    queue.offerFirst(curr.right);
                }
            } else {
                // 如果是奇数层，那么从队头取出节点，先右后左，加入到队尾
                curr = queue.pollFirst();
                if (curr.right != null) {
                    queue.offerLast(curr.right);
                }
                if (curr.left != null) {
                    queue.offerLast(curr.left);
                }
            }
            levelResult.add(curr.val);
        }
        result.add(levelResult);
        depth++;
    }
    return result;
}

42-简述举列二叉树的深度（递归；非递归）

后序遍历二叉树的深度

public int depth() {
    return depth(root);
}

private int depth(TreeNode<E> curr) {
    if (curr == null) {
        return 0;
        // 空树深度为 0，递归结束，开始返回
    } else {
        // 这种情况实际上包含了两种情况：一种是叶子结点，此时返回的是 1；另一种是非叶子结点，返回的是较深子树的深度+1
        // 综合起来就是每遇到叶子结点，深度就加 1，得到子树的深度，最后加上根节点的深度 1
        int leftDepth = depth(curr.left);
        int rightDepth = depth(curr.right);
        return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
    }
}

非递归求深度，采用层序遍历的方式

public int depthNoRec() {
    TreeNode<E> curr;
    Deque<TreeNode<E>> queue = new ArrayDeque<>();
    queue.add(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        // 一层进行遍历, queue 的长度即为该层节点个数
        for (int i = 0; i < levelSize; i++) {
            curr = queue.poll();
            if (curr.left != null) {
                queue.add(curr.left);
            }
            if (curr.right != null) {
                queue.add(curr.right);
            }
        }
        depth++;
    }
    return depth;
}

43-简述如何实现前序遍历重建二叉树

/**
 * 每个节点数据后加一个！，如果是空节点，那么用 # ！表示
 * 比如 12!3!#!#!#!
 * 
 * 12
 * / \
 * 3  null
 * 
 * @param preStr
 * @return
 */
public static BinarySearchTree<String> createStringBiTree(String preStr) {
    String[] pre = preStr.split("!");
    System.out.println(Arrays.toString(pre));
    BinarySearchTree<String> tree = new BinarySearchTree<>(createStringSubTree(pre));
    index = -1;
    return tree;
}

private static TreeNode<String> createStringSubTree(String[] pre) {
    index++;
    TreeNode<String> subTree = null;
    if (!pre[index].equals("#")) {
        subTree = new TreeNode<>(pre[index]);
        subTree.left = createStringSubTree(pre);
        subTree.right = createStringSubTree(pre);
    }
    return subTree;
}

44-简述Java如何实现翻转二叉树？

/**
 * 二叉树反转
 * @param node
 * 微信公众号：程序员乔戈里
 * @return
 */
public TreeNode<E> invert(TreeNode<E> node) {
    if(node != null) {
        if(node.left != null) {
            node.left = invert(node.left);
        }
        if(node.right != null) {
            node.right = invert(node.right);
        }
        TreeNode<E> temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
    return node;
}

45-简述如何判断一棵二叉树是否是另一棵二叉树的子树？

常规解法：二叉树遍历 O(M*N)

N 是原树的节点数，M 是目标树的节点数

子树：在二叉树中以任何一个节点为头部的整棵树称作二叉树的子树

/**
 * 判断 rhs 是否是 lhs 的一棵子树（一直到叶）
 * 注意：
 * {1} 不是 {1,2,3,4,5,6,7} （层序遍历）的子树
 * {1,#,1} 是 {1,1,1,#,1,1,#} 的子树
 * @param lhs
 * @param rhs
 * @return
 */
private boolean isSubTree(TreeNode<E> lhs, TreeNode<E> rhs) {
    // 空树是任何树的子树
    if (rhs == null) {
        return true;
    }
    // lhs 为空且 rhs 不为空，那么一定不是子树
    else if (lhs == null) {
        return false;
    }
    // 从当前节点开始判断是否是相同树
    else if (lhs.val.equals(rhs.val) && isSame(lhs.left, rhs.left) && isSame(lhs.right, rhs.right)) {
        return true;
    } else {
        // 判断左孩子或右孩子的子树关系
        return isSubTree(lhs.left, rhs) || isSubTree(lhs.right, rhs);
    }
}

/**
 * 判断两棵子树是否是一样的
 *
 * @param lhs
 * @param rhs
 * @return
 */
private boolean isSame(TreeNode<E> lhs, TreeNode<E> rhs) {
    if (lhs == null && rhs == null) {
        return true;
    } else if (lhs != null && rhs != null) {
        return lhs.val.equals(rhs.val) && isSame(lhs.left, rhs.left) && isSame(rhs.right, rhs.right);
    } else {
        return false;
    }
}

最优解法：二叉树序列化 + KMP 匹配 O(M+N)

public boolean isSubTreeBySerialization(BinarySearchTree<E> tree) {
    return preOrderToString(root).indexOf(preOrderToString(tree.root)) != -1;
}

public String preOrderToString(TreeNode<E> subTree) {
    StringBuilder sb = new StringBuilder();
    preOrderToString(subTree, sb);
    return sb.toString();
}

private void preOrderToString(TreeNode<E> subTree, StringBuilder sb) {
    if (subTree != null) {
        sb.append(subTree.val).append("!");
        preOrderToString(subTree.left, sb);
        preOrderToString(subTree.right, sb);
    } else {
        sb.append("#!");
    }
}

public int indexOf(MyString str) {
    char[] chars = str.toCharArray();
    int i = 0, j = 0;
    int[] next = getNext(str);
    while (i < value.length && j < chars.length) {
        if (j == -1 || value[i] == chars[j]) {
            // next 数组中存在-1，为了避免越界，增加 j == -1 这个条件
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == chars.length) {
        return i - chars.length;
    } else {
        return -1;
    }
}

private static int[] getNext(MyString str) {
    int[] next = new int[str.length()];
    int i = -1, j = 0;
    char[] chars = str.toCharArray();
    next[0] = -1;
    while (j < chars.length - 1) {
        if (i == -1 || chars[i] == chars[j]) { // 相当于 chars[next[j]] == chars[j]
            i++;
            j++;
            next[j] = i;
        } else {
            i = next[i];
        }
    }
    // j 是主串指针，i 是子串指针
    return next;
}

微信公众号：程序员乔戈里

46-简述平衡二叉树判断（后序遍历）

/**
 * 判断是否是平衡二叉树
 * @return
 */
public boolean isAVL() {
    return isAVL(root);
}

private boolean isAVL(TreeNode<E> curr) {
    if(curr == null) {
        return true;
    }
    // 先判断左右孩子是否是 AVL，如果不是，那么直接返回 false
    // 如果左右孩子都是 AVL，那么判断自己是否是 AVL
    if (isAVL(curr.left) && isAVL(curr.right)) {
        return Math.abs(depth(curr.left) - depth(curr.right)) <= 1;
    } else {
        return false;
    }
}

47-简述二叉搜索树判断（4 种算法，中序遍历最优）

/**
 * 是否是二叉搜索树
 *
 * @return
 */
public boolean isBST() {
    return isBSTByInOrder(root);
}

/**
 * 这个算法是错误的，因为左孩子 < 根 < 右孩子并不能证明 max(左子树) < 根 < min(右孩子)
 */
// private boolean isBSTByQueryingMaxMin(TreeNode<E> curr) {
//     if (curr == null) {
//         return true;
//     }
//     if (isBSTByQueryingMaxMin(curr.left) && isBSTByQueryingMaxMin(curr.right)) {
//         return (curr.left != null ? curr.val.compareTo(curr.left.val) > 0 : true) &&
//             (curr.right != null ? curr.val.compareTo(curr.right.val) < 0 : true);
//     } else {
//         return false;
//     }
// }

/**
 * 时间复杂度是 O(n * h)
 * 原因是每做一次递归（向下走），我们都要去查找最大值和最小值。
 *
 * @param curr
 * @return
 */
private boolean isBSTByQueryingMaxMin(TreeNode<E> curr) {
    if (curr == null) {
        return true;
    }
    if (curr.left != null && findMax(curr.left).val.compareTo(curr.val) > 0) {
        return false;
    }
    if (curr.right != null && findMin(curr.right).val.compareTo(curr.val) < 0) {
        return false;
    }
    return isBSTByQueryingMaxMin(curr.left) && isBSTByQueryingMaxMin(curr.right);
}

/**
 * 不必每次都要去查找最小值和最大值，可以采用参数传递的方式
 * 时间复杂度为 O(n)
 * min 和 max，对于 Integer 而言，是 -2147483648~2147483647
 *
 * @param curr
 * @return
 */
public boolean isBSTByPassingMaxMin(TreeNode<E> curr, E min, E max) {
    if (curr == null) {
        return true;
    }
    if (min.compareTo(curr.val) > 0 || max.compareTo(curr.val) < 0) {
        return false;
    }
    // 对于左子树而言，其最大值为根；对于右子树而言，其最小值为根
    return isBSTByPassingMaxMin(curr.left, min, curr.val) && isBSTByPassingMaxMin(curr.right, curr.val, max);
}

/**
 * 中序遍历得到一个序列，如果是有序的，那么一定是 BST
 * 时间复杂度为 O(n)，空间复杂度为 O(n)
 *
 * @param curr
 * @return
 */
private boolean isBSTByInOrderSequence(TreeNode<E> curr) {
    List<E> inOrderList = inOrderToList(curr);
    for (int i = 1; i < inOrderList.size(); i++) {
        if (inOrderList.get(i - 1).compareTo(inOrderList.get(i)) > 0) {
            return false;
        }
    }
    return true;
}

/**
 * 可以在中序遍历的过程中进行判断，时间复杂度为 O(n)，空间复杂度为 O(1)
 *
 * @param curr
 * @return
 */
private boolean isBSTByInOrder(TreeNode<E> curr) {
    E lastValue = null;
    Stack<TreeNode<E>> stack = new Stack<>();
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            // while 表示不断地访问其左子树，直至达到左子树的最底端
            stack.push(curr);
            curr = curr.left; // 访问左子树
        }
        if (!stack.isEmpty()) {
            curr = stack.pop();
            if (lastValue != null && curr.val.compareTo(lastValue) >= 0) {
                return false;
            }
            lastValue = curr.val;
            curr = curr.right; // 访问右子树
        }
    }
    return true;
}

这里仅对排版进行了优化，内容没有做其他更改。

48-简述Java实现完全二叉树判断（层序遍历）

/**
 * 判断是否是完全二叉树
 * 算法：
 * 微信公众号：程序员乔戈里
 * 
 * 1）采用层序遍历的方式
 * 2）如果左子树为空，且右子树不为空，则返回 false
 * 3）如果左子树不为空，且右子树为空，则后续节点必须全为叶子节点
 * 4）循环结束后返回 true
 * 
 * @return
 */
public boolean isCompleteBinaryTree() {
    Queue<TreeNode<E>> queue = new ArrayDeque<>();
    queue.add(root);
    TreeNode<E> curr;
    boolean nextLeaf = false;
    
    while (!queue.isEmpty()) {
        // 访问节点，检查一些要求
        curr = queue.poll();
        
        // 不符合完全二叉树的定义
        if (curr.left == null && curr.right != null) {
            return false;
        }
        
        // 如果要求本身是叶子节点，但并不是，则退出
        if (nextLeaf && (curr.left != null || curr.right != null)) {
            return false;
        }
        
        // 左孩子不为空，右孩子为空，则后续节点都必须为叶子节点
        if (curr.left != null && curr.right == null) {
            nextLeaf = true;
        }
        
        if (curr.left != null) {
            queue.add(curr.left);
        }
        
        if (curr.right != null) {
            queue.add(curr.right);
        }
    }
    return true;
}

49-简述二叉树求任意节点的后继节点？

后继节点是指中序遍历时的后一个节点。

简单方法：

  1. 通过 node 的 parent 指针不断向上找，得到 root。
  2. 从 root 开始中序遍历，得到中序遍历序列。
  3. 在中序遍历序列中找到 node 的后继节点。

时间复杂度为 O(n)，空间复杂度为 O(n)。

最优解：

如果 node 节点与其后继节点之间的实际距离为 L，最优解只需要走 L 步，时间复杂度为 O(L)，空间复杂度为 O(1)。

/**
 * 时间复杂度为 O(l)，L 为 node 与其后继节点之间的距离，空间复杂度为 O(1)
 * 1）如果 node 有右子树，那么后继节点是其右子树的最左节点。
 * 2）如果 node 没有右子树，那么看 node 是不是其父节点的左孩子，如果是，那么后继节点是 node 的父节点。
 * 3）如果是父节点的右孩子，就向上寻找 node 的后继节点。设置当前节点为 curr，父节点为 parent。
 *    判断 curr == parent.left，则 parent 为 curr 的后继，否则继续向上移动。
 * 4）如果 parent 为 null，那么说明 node 没有后继节点。
 *
 * @param curr
 * @return
 */
public static TreeNode successor(TreeNode curr) {
    if (curr == null) {
        return null;
    }

    // 1) 如果 node 有右子树
    if (curr.right != null) {
        curr = curr.right;
        while (curr.left != null) {
            curr = curr.left;
        }
        return curr;
    } else {
        // 2) 如果 node 没有右子树
        TreeNode parent = curr.parent;
        while (parent != null && parent.left != curr) {
            curr = parent;
            parent = parent.parent;
        }
        return parent;
    }
}

50-简述二叉搜索树查错（中序遍历）？

1）中序遍历收集到数组中
2）遍历数组，如果是第一次前一个元素大于后一个元素，那么记录第一个错误节点为前一个（较大的），第二个错误节点为后一个（较小的）。如果是第二次，那么仅记录第二个错误节点为后一个。

/**
 * 一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，
 * 使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回他们的值。
 * 保证二叉树中结点的值各不相同。
 * 给定一棵树的根结点，请返回两个调换了位置的值
 * 
 * 1）中序遍历收集到数组中
 * 2）遍历数组，如果是第一次前一个元素大于后一个元素，
 *    那么记录第一个错误节点为前一个（较大的），第二个错误节点为后一个（较小的）。
 *    如果是第二次，那么仅记录第二个错误节点为后一个。
 * 
 * @return
 */
public E[] findBSTErrorNodes() {
    List<E> inOrderList = inOrderToList(root);
    E first = null;
    E second = null;
    for (int i = 1; i < inOrderList.size(); i++) {
        if (inOrderList.get(i - 1).compareTo(inOrderList.get(i)) > 0) {
            if (first == null) {
                first = inOrderList.get(i - 1);
            }
            second = inOrderList.get(i);
        }
    }
    return (E[]) new Object[]{first, second};
}

51-简述二叉树节点间最大距离（后序遍历）

private static class Distance {
    int max;
    int maxFromChild;

    public Distance(int max, int maxFromChild) {
        this.max = max;
        this.maxFromChild = maxFromChild;
    }
}

public int getLongestDistanceBetweenNodes() {
    return getLongestDistanceBetweenNodes(root).max;
}

/**
 * 空节点的 max 为 0 ， maxFromChild 为 0
 * 叶子节点的 max 为 1 ， maxFromChild 为 1
 * 每个节点的 max = MAX(leftMax, rightMax, 1 + maxFromLeft + maxFromRight)
 * 每个节点的 maxFromChild = MAX(leftMax, rightMax) + 1
 * 
 * @param curr
 * @return
 */
private Distance getLongestDistanceBetweenNodes(TreeNode<E> curr) {
    if (curr != null) {
        Distance leftDistance = getLongestDistanceBetweenNodes(curr.left);
        Distance rightDistance = getLongestDistanceBetweenNodes(curr.right);
        
        return new Distance(
            Math.max(
                Math.max(leftDistance.max, rightDistance.max),
                leftDistance.maxFromChild + rightDistance.maxFromChild + 1
            ),
            Math.max(leftDistance.maxFromChild, rightDistance.maxFromChild) + 1
        );
    } else {
        return new Distance(0, 0);
    }
}

This version focuses on improving the readability and layout of the code for better understanding and presentation.

52-简述二叉树中的最大二叉搜索子树（后序遍历）

算法：

1）收集左子树的四个信息（最大搜索二叉子树的头结点，节点数，树上最小值，树上最大值），
收集右子树的四个信息（最大搜索二叉子树的头结点，节点数，树上最小值，树上最大值）。

2）更新根节点的最小值和最大值。

3）判断是否整体都是搜索二叉树，如果是，则返回根（先更新 MaxSubBSTRoot 和 size）；
如果不是，就返回左子树和右子树各自的最大搜索二叉树中，节点数较多的那个树的（MaxSubBSTRoot 和 size）。

代码：

static class MaxBSTInfo {
    TreeNode<Integer> maxSubBSTRoot;
    int size;
    int min;
    int max;

    public MaxBSTInfo() {
    }

    public MaxBSTInfo(TreeNode<Integer> maxSubBSTRoot, int size, int min, int max) {
        this.maxSubBSTRoot = maxSubBSTRoot;
        this.size = size;
        this.min = min;
        this.max = max;
    }

    @Override
    public String toString() {
        return "MaxBSTInfo{" +
                "maxSubBSTRoot=" + (maxSubBSTRoot != null ? maxSubBSTRoot.val : "null") +
                ", size=" + size +
                ", min=" + min +
                ", max=" + max +
                '}';
    }
}

/**
 * 1）收集左子树的四个信息（最大搜索二叉子树的头结点，节点数，树上最小值，树上最大值），
 * 收集右子树的四个信息（最大搜索二叉子树的头结点，节点数，树上最小值，树上最大值）。
 * 2）更新根节点的最小值和最大值。
 * 3）判断是否整体都是搜索二叉树，如果是，则返回根（先更新 MaxSubBSTRoot 和 size）；
 * 如果不是，就返回左子树和右子树各自的最大搜索二叉树中，节点数较多的那个树的（MaxSubBSTRoot 和 size）。
 *
 * @param curr
 * @return
 */
public MaxBSTInfo getMaxSubBSTInfo(TreeNode<Integer> curr) {
    if (curr == null) {
        return new MaxBSTInfo(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
    MaxBSTInfo leftInfo = getMaxSubBSTInfo(curr.left);
    MaxBSTInfo rightInfo = getMaxSubBSTInfo(curr.right);
    MaxBSTInfo rootInfo = new MaxBSTInfo();
    
    rootInfo.max = Math.max(rightInfo.max, curr.val);
    rootInfo.min = Math.min(leftInfo.min, curr.val);
    
    if (leftInfo.maxSubBSTRoot == curr.left && rightInfo.maxSubBSTRoot == curr.right &&
        leftInfo.max < curr.val && curr.val < rightInfo.min) {
        rootInfo.maxSubBSTRoot = curr;
        rootInfo.size = leftInfo.size + rightInfo.size + 1;
        return rootInfo;
    } else {
        if (leftInfo.size >= rightInfo.size) {
            rootInfo.maxSubBSTRoot = leftInfo.maxSubBSTRoot;
            rootInfo.size = leftInfo.size;
            return rootInfo;
        } else {
            rootInfo.maxSubBSTRoot = rightInfo.maxSubBSTRoot;
            rootInfo.size = rightInfo.size;
            return rootInfo;
        }
    }
}

53-简述Java如何前中序遍历重建二叉树

public static BinarySearchTree<Character> preInCreateBiTreeUseSubString(String pre, String in) {
    return new BinarySearchTree<>(createSubTreeUseSubString(pre, in));
}

// 这个算法更好，不使用下标，直接取子串
private static TreeNode<Character> createSubTreeUseSubString(String pre, String in) {
    TreeNode<Character> subTree = null;
    if (pre.length() == 0) {
        return null;
    } else {
        subTree = new TreeNode<>(pre.charAt(0));
        int mid = in.indexOf(pre.charAt(0));
        subTree.left = createSubTreeUseSubString(pre.substring(1, mid + 1), in.substring(0, mid));
        subTree.right = createSubTreeUseSubString(pre.substring(mid + 1), in.substring(mid + 1));
    }
    return subTree;
}

54 - 简述二叉树判断是否对称（先序遍历）

比如层序遍历结果为：8 6 6 5 7 7 5

/**
 * 是否是对称的二叉树
 * 先序遍历
 * 注意对称不是指的是左右孩子值相同，而是左孩子的左孩子值等于右孩子的右孩子值。
 * 左孩子的右孩子值等于右孩子的左孩子值
 *
 * @return
 */
public boolean isSymmetrical() {
    return isSymmetrical(root, root);
}

private boolean isSymmetrical(TreeNode<E> currA, TreeNode<E> currB) {
    if (currA == null && currB == null) {
        return true;
    }
    if (currA == null || currB == null) {
        return false;
    }
    if (currA.val != currB.val) {
        return false;
    }
    return isSymmetrical(currA.left, currB.right) &&
           isSymmetrical(currA.right, currB.left);
}

55 - 简述 Java 如何打印二叉树的所有路径（先序遍历）

问题描述：
输出二叉树从根节点到每个叶子结点的路径

public void printAllBiTreePaths() {
    printBiTreePath(root, new LinkedList<>());
}

/**
 * 微信公众号：程序员乔戈里
 * 类似于先序遍历
 * @param node 当前节点
 */
private void printBiTreePath(TreeNode<E> node, LinkedList<TreeNode<E>> pathList) {
    if (node != null) {
        pathList.addLast(node);
        if (node.left == null && node.right == null) {
            for (TreeNode<E> treeNode : pathList) {
                System.out.print(treeNode.val + " ");
            }
            System.out.println();
            // 输出链表从根节点到叶子的数据域
        } else {
            printBiTreePath(node.left, pathList);
            printBiTreePath(node.right, pathList);
        }
        pathList.removeLast();
        // 处理完当前结点，退出链表
    }
}

56-简述二叉树中和为某值的所有路径？

输出二叉树从根节点到每个叶子结点的路径

public List<List<Integer>> findPathSumEquaiTo(TreeNode<Integer> root, int expectedSum) {
    List<List<Integer>> result = new ArrayList<>();
    findPathSumEqualTo(root, new LinkedList<Integer>(), result, 0, expectedSum);
    return result;
}

/**
 * 类似于先序遍历
 * @param node
 */
private void findPathSumEqualTo(TreeNode<Integer> node, LinkedList<Integer> pathList, 
                                 List<List<Integer>> result, int currentSum, int expectedSum) {
    if (node != null) {
        pathList.addLast(node.val);
        currentSum += node.val;

        if (node.left == null && node.right == null && currentSum == expectedSum) {
            result.add(new ArrayList<>(pathList));
            System.out.println();  // 输出链表从根节点到叶子的数据域
        } else {
            findPathSumEqualTo(node.left, pathList, result, currentSum, expectedSum);
            findPathSumEqualTo(node.right, pathList, result, currentSum, expectedSum);
        }

        pathList.removeLast();  // 处理完当前结点，退出链表
    }
}

57-简述二叉搜索树转为有序双向链表（中序遍历）？

/**
 * 二叉搜索树转为有序双向链表
 * 非递归中序遍历
 * @param curr
 * @return
 */
public TreeNode<E> BST2DoubleLinkedList(TreeNode<E> curr) {
    Stack<TreeNode<E>> stack = new Stack<>();
    TreeNode<E> pre = null;
    TreeNode<E> head = null;
    
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        
        if (!stack.isEmpty()) {
            curr = stack.pop();
            
            // 新增部分代码
            if (head == null) {
                head = curr;
            }
            
            // 重建指针
            curr.left = pre;
            if (pre != null) {
                // 重建指针
                pre.right = curr;
            }
            
            pre = curr;
            
            // 结束
            curr = curr.right; // 访问右子树
        }
    }
    return head;
}

微信公众号：程序员乔戈里

58 - 简述如何实现二叉搜索树的第 k 个节点（从小到大）？

/**
 * 中序遍历 求从小到大的第 k 个 node
 * @param k
 * @return
 */
public E kthNodeInBST(int k) {
    TreeNode<E> curr = root;
    Stack<TreeNode<E>> stack = new Stack<>();
    
    while (curr != null || !stack.isEmpty()) {
        // while 表示不断地访问其左子树，直至达到左子树的最底端
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;  // 访问左子树
        }
        
        if (!stack.isEmpty()) {
            curr = stack.pop();
            k--;
            if (k == 0) {
                return curr.val;
            }
            curr = curr.right;  // 访问右子树
        }
    }
    
    return null;
}

59 - 简述如何计算二叉树父节点（先序遍历）？

public TreeNode<E> parent(TreeNode<E> curr) {
    if (curr == null) {
        return null;
    }
    return parent(root, curr);
}

/**
 * 先序遍历
 * @param root
 * @param curr
 * @return
 */
private TreeNode<E> parent(TreeNode<E> root, TreeNode<E> curr) {
    TreeNode<E> parent;
    if (root == null) {
        return null;
    } else {
        if (root.left == curr || root.right == curr) {
            return root;
        } else {
            parent = parent(root.left, curr);
            // 在左子树中递归搜索 element 的父节点
            return parent != null ? parent : parent(root.right, curr);
            // 如果在左子树中找到了，就返回；没有找到，就在右子树中搜索
            // 如果都没有找到，就返回 null
        }
    }
}

60-简述如何计算二叉树第 k 层节点个数？

public int sizeOfLevel(int k) {
    return sizeOfLevel(root, k);
}

/**
 * 第 k 层节点个数就是第 k-1 层的孩子数
 * k == 0 时，返回 1 或 0
 * @param curr 当前节点
 * @param k 当前层数
 * @return 第 k 层的节点个数
 */
private int sizeOfLevel(TreeNode<E> curr, int k) {
    if (curr == null) {
        return 0;
    }
    if (k == 0) {
        return 1;
    } else {
        return sizeOfLevel(curr.left, k - 1) + sizeOfLevel(curr.right, k - 1);
    }
}

解释：

  • sizeOfLevel(int k) 方法是公开的接口，调用时传入层数 k，会返回第 k 层的节点个数。
  • sizeOfLevel(TreeNode<E> curr, int k) 是递归方法，计算当前节点的左右子树中第 k 层节点的个数。
  • 当 k == 0 时，表示到达第 k 层，此时返回 1（表示当前节点）。
  • 当 k > 0 时，递归计算左子树和右子树的第 k-1 层节点的个数。

61-简述Java有序数组重建 BST AVL

/**
 * 有序数组重建二叉搜索树
 * 时间复杂度为 O(n)
 * @param arr
 * @param low
 * @param high
 * @return
 */
public static TreeNode fromArray(int[] arr, int low, int high) {
    if (low > high) {
        return null;
    }
    if (low == high) {
        return new TreeNode(arr[low]);
    }
    int mid = (low + high) / 2;
    TreeNode root = new TreeNode(arr[mid]);
    root.left = fromArray(arr, low, mid - 1);
    root.right = fromArray(arr, mid + 1, high);
    return root;
}

62 - 简述 Java 如何有序链表重建 BST (AVL)？

/**
 * 有序链表转 BST
 * @param head
 * @return
 */
public static TreeNode fromLinkedList(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.next == null) {
        return new TreeNode(head.val);
    }

    ListNode slow = head, fast = head, pre = null;
    while (fast.next != null && fast.next.next != null) {
        pre = slow;
        fast = fast.next.next;
        slow = slow.next;
    }

    // 希望将链表拆为三部分：左子树，根，右子树
    // 根是 slow, 右子树是从 slow.next 开始的
    if (pre != null) {
        pre.next = null;
    }

    TreeNode root = new TreeNode(slow.val);
    root.left = fromLinkedList(slow == head ? null : head);
    root.right = fromLinkedList(slow.next);

    return root;
}

63-简述Java数组实现循环队列

public class MyQueue<E> {
    private Object[] value;  // 存储队列元素的数组
    private int front;       // 指向头结点
    private int rear;        // 指向尾结点的下一个结点
    private int elements;    // 有效元素个数

    // 构造函数，初始化队列
    public MyQueue(int length) {
        if (length <= 0) {
            throw new IndexOutOfBoundsException("长度必须大于 0");
        }
        value = new Object[length];
    }

    // 入队
    public void enQueue(E e) {
        if (isFull()) {
            return;
        }
        value[rear] = e;
        rear = (rear + 1) % value.length;  // 循环队列的关键
        elements++;
    }

    // 出队
    public E deQueue() {
        if (isEmpty()) {
            return null;
        }
        Object obj = value[front];
        value[front] = null;
        front = (front + 1) % value.length;  // 循环队列的关键
        elements--;
        return (E) obj;
    }

    // 查看队头元素
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) value[front];
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return elements == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return elements == value.length;
    }

    // 获取队列的大小
    public int size() {
        return elements;
    }

    // 遍历队列
    public void traverse() {
        System.out.print("[");
        int j = front;
        for (int i = 0; i < elements; i++) {  // 遍历次数用 elements 来决定
            System.out.print(value[j] + (i + 1 == elements ? "" : ","));
            j = (j + 1) % value.length;  // 循环队列的关键
        }
        System.out.println("]");
    }
}

此代码实现了一个基于数组的循环队列，通过 front 和 rear 指针控制队列的头尾元素，使用 % value.length 来实现循环效果。队列满时，rear 会绕回数组的起始位置。

64-简述Java可以查询最值的栈

第一种稍省空间，第二种稍省时间。

public class QueryMinStack {
    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        dataStack.push(node);
        // 第一种
        if(minStack.isEmpty() || node < minStack.peek()) {
            minStack.push(node);
        }
    }

    public int pop() {
        if(dataStack.isEmpty()) {
            throw new IllegalStateException("空");
        }
        int data = dataStack.pop();
        if(data == minStack.peek()) {
            minStack.pop();
        }
        return data;
    }

    public int top() {
        if(dataStack.isEmpty()) {
            throw new IllegalStateException("空");
        }
        return dataStack.peek();
    }

    public int min() {
        if(minStack.isEmpty()) {
            throw new IllegalStateException("空");
        }
        return minStack.peek();
    }
}

65-简述Java双栈实现队列

public class TwoStackQueue {
    private Stack<Integer> pushStack = new Stack<>();
    private Stack<Integer> popStack = new Stack<>();

    // 将元素添加到 pushStack 中
    public void offer(int node) {
        pushStack.push(node);
    }

    /**
     * 如果 popStack 为空的话，将 pushStack 倒入 popStack，
     * 否则就等 popStack 全部弹出后再倒入，避免顺序混乱
     * @return 返回队列中的第一个元素
     */
    public int poll() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
        return popStack.pop();
    }

    // 查看队列中的第一个元素
    public int peek() {
        if (popStack.isEmpty()) {
            throw new IllegalStateException("空");
        }
        return popStack.peek();
    }
}

以上是优化后的排版格式，仅进行格式和结构上的改进。

66-简述Java实现栈逆序

/**
 * 栈逆序
 * @param stack
 */
public static void reverse(Stack<Integer> stack) {
    if (!stack.isEmpty()) {
        int bottom = popBottom(stack);
        reverse(stack);
        stack.push(bottom);
    }
}

/**
 * 弹出栈底
 * @param stack
 * @return
 */
private static int popBottom(Stack<Integer> stack) {
    int data = stack.pop();
    
    // 不是栈底，则重新压回，并将栈底的结果返回
    if (!stack.isEmpty()) {
        int bottom = popBottom(stack);
        stack.push(data);
        return bottom;
    } else {
        // pop 完为空，说明是栈底了
        // 栈底不重新压回栈中
        return data;
    }
}

这个优化后的排版格式在代码的可读性和清晰度上有所提升，方法和注释得到了良好的分隔和解释。

67-简述实现Java双栈排序

public static void sort(Stack<Integer> stack) {
    Stack<Integer> helpStack = new Stack<>();
    int element;
    
    while(!stack.isEmpty()) {
        element = stack.pop();
        
        if(helpStack.isEmpty() || element <= helpStack.peek()) {
            helpStack.push(element);
        } else {
            // 仅将小于 element 的压回 stack
            while(!helpStack.isEmpty() && element > helpStack.peek()) {
                stack.push(helpStack.pop());
            }
            helpStack.push(element);
        }
    }
    
    while(!helpStack.isEmpty()) {
        stack.push(helpStack.pop());
    }
}

68 - 简述Java实现数组转类似于大顶堆的二叉树 MaxTree？

设置一个栈，要求栈从栈底到栈顶是从大到小的序列，栈顶元素是最小值，入栈元素必须比栈顶元素要小。

求 leftFirstUpper（每个数左边第一个比它大的数）要求顺序遍历数组。
栈先压入 3，比较 1 和栈顶，因为 1 < 栈顶，所以记录 leftFirstUpper(1) = 3，然后将 1 压入。
比较 2 和栈顶，2 > 栈顶，出栈，比较 2 和当前栈顶，直至 2 < 栈顶，记录 leftFirstUpper(2) = 3。

rightFirstUpper 同理，只是遍历元素时逆序遍历。
根据上述结果可以得到整棵树：每棵树的根节点是左边第一个大的数和右边第一个大的数较小的一个。
整个数组的最大值是整棵树的根节点。

parent(5) = null  
parent(2) = 5  
parent(4) = 5  
parent(1) = 2  
parent(3) = 4

这个方法可以保证：

  • 整棵树的根节点只有一个；是二叉树。

为什么可以保证是二叉树？

任何一个数在单独一侧，孩子的数量一定不超过 1 个。
例如：A, A > K1, A > K2
假设 K1 > K2，那么 parent(K2) = K1，parent(K1) = A，不存在 parent(K2) = A，parent(K1) = A。

以【3, 4, 5, 1, 2】为例：
leftFirstUpperValueIndex 为：【-1, -1, -1, 2, 2】
rightFirstUpperValueIndex 为：【1, 2, -1, 4, -1】
parent 为：【1, 2, -1, 4, 2】

代码实现：

/**
 * 给定一个没有重复元素的数组 arr，将 arr 转为一颗二叉树，
 * 该二叉树要求满足如下性质：
 * 1 ）数组的每一个值对应二叉树的一个节点
 * 2 ）包括整棵树在内的每一棵子树，值最大的节点都是根节点。
 * 这种二叉树和大顶堆很类似，只是大顶堆还要求必须是完全二叉树。
 * 最优解的时间复杂度为 O(n) ，空间复杂度为 O(n)
 * 算法：
 * 1 ）需要计算每个数左边第一个比它大的数和右边第一个比它小的数。
 * 求 leftFirstUpper （每个数左边第一个比它大的数），要求栈从栈底到栈顶是从大到小的
 * 序列。
 * rightFirstUpper 同理，只是需要逆序遍历
 * 2 ）将 1 ）中的表转为父子关系表：
 * 遍历数组，如果左右第一个比它大的有不为空的，就取不为空的数作为其父节点；
 * 如果都不为空，那么取值较小的数作为其父节点
 *
 * @param arr
 * @return 每个元素为原数组中对应位置元素在树中的父亲节点的编号，若为根则值为 -1
 */
public static int[] buildMaxTree(int[] arr) {
    // 注意，arr[i]的左边第一个比它大的数的下标为 leftFirstUpper[i],
    // 右边第一个比它大的数的下标为 rightFirstUpper[i]
    int[] leftFirstUpperValueIndex = new int[arr.length];
    int[] rightFirstUpperValueIndex = new int[arr.length];
    Arrays.fill(leftFirstUpperValueIndex, -1);
    Arrays.fill(rightFirstUpperValueIndex, -1);

    // 该栈的栈顶是整个栈中的对应的数值中的最小值的索引
    // 入栈元素要求比栈顶还要小
    Stack<Integer> indexMinStack = new Stack<>();

    // 1)求得两张表
    for (int i = 0; i < arr.length; i++) {
        while (!indexMinStack.isEmpty() && arr[i] > arr[indexMinStack.peek()]) {
            indexMinStack.pop();
        }
        // 此时 arr[i]一定小于栈顶
        // 记录
        if (!indexMinStack.isEmpty()) {
            leftFirstUpperValueIndex[i] = indexMinStack.peek();
        }
        indexMinStack.push(i);
    }

    indexMinStack.clear();

    // 逆序遍历
    for (int i = arr.length - 1; i >= 0; i--) {
        while (!indexMinStack.isEmpty() && arr[i] > arr[indexMinStack.peek()]) {
            indexMinStack.pop();
        }
        // 此时 arr[i]一定小于栈顶
        // 记录
        if (!indexMinStack.isEmpty()) {
            rightFirstUpperValueIndex[i] = indexMinStack.peek();
        }
        indexMinStack.push(i);
    }

    // 2)根据两张表求得树节点之间的父子关系
    int[] parent = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        parent[i] = getLowerValueIndex(arr, leftFirstUpperValueIndex[i], rightFirstUpperValueIndex[i]);
    }
    return parent;
}

private static int getLowerValueIndex(int[] arr, int leftFirstUpperValueIndex, int rightFirstUpperValueIndex) {
    int leftValue = getValue(arr, leftFirstUpperValueIndex);
    int rightValue = getValue(arr, rightFirstUpperValueIndex);

    // 优先返回不为空的，都不为空的话就返回较小数值的索引
    if (leftValue != -1 && rightValue != -1) {
        return leftValue < rightValue ? leftFirstUpperValueIndex : rightFirstUpperValueIndex;
    } else {
        return leftValue != -1 ? leftFirstUpperValueIndex : rightFirstUpperValueIndex;
    }
}

private static int getValue(int[] arr, int i) {
    if (i == -1) {
        return -1;
    } else {
        return arr[i];
    }
}

69 - 简述调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

示例：

  • 输入：0 2 4 6 1 3 5

    1. 5 2 4 6 1 3 0
    2. 5 3 4 6 1 2 0
    3. 5 3 1 6 4 2 0

方法一：moveOddToFront

public static void moveOddToFront(int[] arr) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low < high) {
        while (low < high && (arr[low] & 1) == 1) {
            low++;
        }
        while (low < high && (arr[high] & 1) == 0) {
            high--;
        }
        if (low < high) {
            swap(arr, low, high);
        }
    }
}

方法二：moveOddToFrontFaster

public static void moveOddToFrontFaster(int[] arr) {
    int afterOdd = 0;
    for (int i = arr.length - 1; i >= afterOdd; ) {
        if ((arr[i] & 1) == 1) {
            swap(arr, i, afterOdd);
            afterOdd++;
        } else {
            i--;
        }
    }
}

方法三：moveOddToFrontWithFixedRelativePosition

public static void moveOddToFrontWithFixedRelativePosition(int[] arr) {
    Queue<Integer> queue = new ArrayDeque<>();
    int evenCount = 0;

    for (int i = 0; i < arr.length; i++) {
        // 如果是奇数，放到 i-evenCount 位置
        if ((arr[i] & 1) == 1) {
            arr[i - evenCount] = arr[i];
        } else {
            // 偶数保存到队列中
            queue.add(arr[i]);
            evenCount++;
        }
    }
    
    // 将偶数顺序放到数组后面
    for (int i = arr.length - evenCount; i < arr.length; i++) {
        arr[i] = queue.remove();
    }
}

辅助方法：swap

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

70 - 简述 Java 实现栈的压入、弹出序列是否匹配？

/**
* [1,2,3,4,5] 是压入序列，那么 [4,5,3,2,1] 是它的一个弹出序列，
* 但 [4,3,5,1,2] 不是。
*
* @param pushSequence 压入序列
* @param popSequence  弹出序列
* @return            是否匹配
*/
public static boolean isMatch(int[] pushSequence, int[] popSequence) {
    Stack<Integer> stack = new Stack<>();
    int pushIndex = 0;
    for (int popIndex = 0; popIndex < popSequence.length; popIndex++) {
        while (stack.isEmpty() || popSequence[popIndex] != stack.peek()) {
            if (pushIndex == pushSequence.length) {
                return false;
            }
            stack.push(pushSequence[pushIndex++]);
        }
        stack.pop();
    }
    return true;
}

71 - 简述 Java 实现逆序打印链表

/**
 * 逆序打印链表
 * 时间复杂度为 O(n)，空间复杂度为 O(n)
 * @param head
 * @return
 */
public static List<Integer> printInversely(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    
    // 将链表元素压入栈中
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    
    List<Integer> result = new ArrayList<>();
    
    // 从栈中弹出元素，形成逆序
    while (!stack.isEmpty()) {
        result.add(stack.pop());
    }
    
    return result;
}

72-简述Java实现单链表翻转

/**
 * 单链表翻转
 * 三个指针： pre ， curr ， post
 * 0) 进入循环前
 * 1 -> 2 -> 3 -> 4 -> 5
 * pre curr post
 *
 * 1) 第一次循环，仅将头节点 next 置为 null
 * 1 -> 2 -> 3 -> 4 -> 5
 * pre curr post
 * 2)
 * 1 <- 2 -> 3 -> 4 -> 5
 * pre curr post
 * 3)
 * 1 <- 2 <- 3 -> 4 -> 5
 * pre curr post
 * 4)
 * 1 <- 2 <- 3 <- 4 -> 5
 * pre curr post
 * 5) 循环结束
 * 1 <- 2 <- 3 <- 4 <- 5
 * pre curr post
 */
public void reverse() {
    if (head == null || head.next == null) {
        return;
    }
    Node<E> backupHead = head;
    Node<E> pre = null;
    Node<E> curr = head;
    Node<E> post = curr.next;

    while (post != null) {
        // 翻转！
        curr.next = pre;
        // 前进！
        pre = curr;
        curr = post;
        post = post.next;
    }

    // 最后一次翻转！
    curr.next = pre;
    // 赋值成员变量
    head = curr;
    tail = backupHead;
}

73 - 简述 Java 实现有序循环链表插入

/**
 * arr 是有序数组， next 是 A 的每个元素的后继下标
 * val 是待插入的元素
 * 1. 链表为空，直接插在头部，并作为 head 返回。
 * 2. 插入元素小于 head 的元素，插于头部之前。必须先遍历到最后一个结点，再插入，并修
 * 改头部，然后返回！
 * 3. 插入元素在中间或者在尾部，在中间就是普通插入方法，
 * 在尾部意思就是它是所有元素最大的元素，插入尾部后让它的 next 指向 head ，
 * 但是，不更新 head ！这就是和 2 情况的不同，所以 2 和 3 情况不能完全合并！必须在情况 2
 * 中更新 head ！
 *
 * @param arr
 * @param next
 * @param val
 * @return
 */
public static ListNode insert(int[] arr, int[] next, int val) {
    ListNode head = buildCircuitLinkedList(arr, next);
    if (head == null) {
        head = new ListNode(val);
        head.next = head;
    } else if (val <= head.val) {
        // 插头
        ListNode last = head;
        while (last.next != head) {
            last = last.next;
        }
        // node 此时指向最后一个节点
        ListNode newHead = new ListNode(val);
        newHead.next = head;
        last.next = newHead;
        head = newHead;
    } else {
        // 插入中间或者尾部
        ListNode curr = head; // 当前节点
        ListNode post = head.next; // 下一个节点
        while (post != head && post.val < val) {
            curr = post;
            post = post.next;
        }
        // 此时 post.val >= val
        // val 将被插到 curr 后面，post 前面 curr.val < val < post.val
        // 也有可能是插入到尾部，post 为 head，curr 为尾节点
        ListNode newNode = new ListNode(val);
        newNode.next = post;
        curr.next = newNode;
    }
    return head;
}

private static ListNode buildCircuitLinkedList(int[] arr, int[] next) {
    if (arr.length == 0) {
        return null;
    }
    ListNode head = new ListNode(arr[0]);
    ListNode tail = head;
    // 最后一个不用创建，一定是 head
    for (int i = next[0]; i != 0; i = next[i]) {
        ListNode newNode = new ListNode(arr[i]);
        tail.next = newNode;
        tail = newNode;
    }
    tail.next = head;
    return head;
}

此代码对链表进行插入操作，插入规则如下：

  1. 如果链表为空，则插入元素作为头节点并将其指向自己。
  2. 如果插入的元素比当前头节点的值小，则插入到头部，并更新头节点。
  3. 如果插入的元素在中间或尾部，则根据值大小定位插入位置，确保链表依旧有序。

解释：

  • arr：存储有序数组。
  • next：存储每个元素的后继节点下标。
  • val：待插入的元素。

上述代码通过遍历链表，根据条件决定如何插入元素，确保链表始终有序，并处理了循环链表的特殊性。

74 - 简述 Java 实现单链表删除当前节点

不给出单链表的头节点，并且要求时间复杂度为 O(1)

public E remove(Node<E> node) {
    E e = node.data;
    if (node == head) {
        return removeFirst();
    } else if (node == tail) {
        return removeLast();
    } else {
        // 删除节点
        // node.next 一定不为空
        node.data = node.next.data;
        node.next = node.next.next;
        size--;
    }
    return e;
}

// 移除头结点
public E removeFirst() {
    checkEmpty();
    Node<E> node = head.next; // 用来保存头结点的下一个结点
    E e = head.data;
    if (node == null) {
        head = tail = null;
    } else {
        head = node;
    }
    size--;
    return e;
}

public E removeLast() {
    checkEmpty();
    Node<E> node = head;
    while (node.next != tail) {
        node = node.next;
    }
    E e = tail.data;
    node.next = null;
    tail = node;
    size--;
    return e;
}

这样排版更清晰，逻辑结构一目了然。

75-简述链表分化（按与某值比较结果分化为三条小链表）？

最优解：将一个链表转为三个小链表，然后再链到一起。

题目描述：

给定一个链表的头节点，再给一个数字 num，将链表调整为节点值小于 num 的节点都放在左边，等于的放在中间，大于的放在右边。

简单做法：
链表转数组，三色排序问题 / 荷兰国旗问题。需要额外空间。

最优解：
将一个链表转为三个小链表，然后再链到一起。

代码实现：

/**
 * @param head 链表头节点
 * @param val 分化的值
 * @return 新链表头节点
 */
public static ListNode partition(ListNode head, int val) {
    ListNode lowerHead = null, equalHead = null, upperHead = null;
    ListNode lowerTail = null, equalTail = null, upperTail = null;
    ListNode curr = head, post;

    // 遍历链表，将节点按值分配到三个链表
    while (curr != null) {
        post = curr.next;
        // 避免遗留的指针影响
        curr.next = null;

        if (curr.val < val) {
            if (lowerHead == null) {
                lowerTail = lowerHead = curr;
            } else {
                lowerTail.next = curr;
                lowerTail = curr;
            }
        } else if (curr.val > val) {
            if (upperHead == null) {
                upperTail = upperHead = curr;
            } else {
                upperTail.next = curr;
                upperTail = curr;
            }
        } else {
            if (equalHead == null) {
                equalTail = equalHead = curr;
            } else {
                equalTail.next = curr;
                equalTail = curr;
            }
        }
        curr = post;
    }

    // 将三条链表连接起来
    // 注意需要考虑每条链表为空的情况
    if (lowerHead != null) {
        if (equalHead != null) {
            lowerTail.next = equalHead;
        } else {
            // 中间链表为空，跳过
            lowerTail.next = upperHead;
        }
    }
    if (equalHead != null) {
        equalTail.next = upperHead;
    }

    return lowerHead != null ? lowerHead : equalHead != null ? equalHead : upperHead;
}

76-简述调整链表顺序使奇数位于偶数前面

/**
 * 链表分化为两条小链表，再接在一起
 * @param head
 * @return
 */
public static ListNode moveOddToFrontWithFixedRelativePosition(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode oddHead = null, oddTail = null;
    ListNode evenHead = null, evenTail = null;

    while (head != null) {
        if ((head.val & 1) == 1) {
            if (oddHead == null) {
                oddTail = oddHead = head;
            } else {
                oddTail.next = head;
                oddTail = oddTail.next;
            }
        } else {
            if (evenHead == null) {
                evenTail = evenHead = head;
            } else {
                evenTail.next = head;
                evenTail = evenTail.next;
            }
        }
        head = head.next;
    }

    // 合并
    if (oddTail != null) {
        oddTail.next = evenHead;
    }
    if (evenTail != null) {
        evenTail.next = null;
    }

    return oddHead != null ? oddHead : evenHead;
}

77 - 简述 Java 两个有序链表的公共值

public static int[] printCommon(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return new int[0];
    }
    List<Integer> common = new ArrayList<>();
    while (headA != null && headB != null) {
        if (headA.val < headB.val) {
            headA = headA.next;
        } else if (headA.val > headB.val) {
            headB = headB.next;
        } else {
            // equal
            common.add(headA.val);
            headA = headA.next;
            headB = headB.next;
        }
    }
    return common.stream().mapToInt(Integer::intValue).toArray();
}

78 - 简述 Java 如何实现链表每 K 个节点间逆序？

方法一

使用栈来处理，栈长度为 k。时间复杂度为 O(n)，空间复杂度为 O(k)。

每 k 个元素入栈，然后重新出栈，这样就实现了逆序。但是实现起来非常复杂：

  1. 入栈出栈后需要进行指针重连
  2. 每组（每 k 个）之间需要进行重连
  3. 第一组需要特殊处理

方法二

每收集 k 个元素就进行逆序，还是需要每组之间进行重连。时间复杂度为 O(n)，空间复杂度为 O(1)。

/**
 * 有一个单链表，请设计一个算法，使得每 K 个节点之间逆序，
 * 如果最后不够 K 个节点一组，则不调整最后几个节点。
 * 例如链表 1->2->3->4->5->6->7->8->null ， K=3 这个例子。
 * 调整后为， 3->2->1->6->5->4->7->8->null 。因为 K==3 ，
 * 所以每三个节点之间逆序，但其中的 7 ， 8 不调整，因为只有两个节点不够一组。
 * 
 * 给定一个单链表的头指针 head, 同时给定 K 值，返回逆序后的链表的头指针。
 * 每收集 k 个元素就进行逆序，还是需要每组之间进行重连。
 * 时间复杂度为 O(n)，空间复杂度为 O(1)。
 *
 * @param head
 * @param k
 * @return
 */
public static ListNode inverse(ListNode head, int k) {
    ListNode resultHead = null;
    ListNode lastGroupTail = null;
    ListNode nextGroupHead = null;
    ListNode curr = head;
    int i = 0;
    
    // 如果链表长度为 k 的整数倍，那么要依赖这个条件退出
    while (curr != null) {
        for (; i < k - 1 && curr.next != null; ++i) {
            curr = curr.next;
        }
        
        // 够 k 个
        if (i == k - 1) {
            // 此时 curr 为新的 head，head 为 tail
            i = 0;
            nextGroupHead = curr.next;
            inverse(head, curr);
        } else {
            // 当前组元素个数不足 k，退出
            if (lastGroupTail == null) {
                resultHead = head;
            } else {
                lastGroupTail.next = head;
            }
            break;
        }
        
        if (resultHead == null) {
            resultHead = curr;
        }
        if (lastGroupTail != null) {
            lastGroupTail.next = curr;
        }
        lastGroupTail = head;
        head = nextGroupHead;
        curr = head;
    }
    return resultHead;
}

private static void inverse(ListNode head, ListNode tail) {
    ListNode pre = null, curr = head, post = head.next;
    
    while (curr != tail) {
        curr.next = pre;
        pre = curr;
        curr = post;
        post = post.next;
    }
    // curr == tail
    curr.next = pre;
}

79 - 简述 Java 编程实现链表删除指定值

public static ListNode remove(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if (head.val == val) {
        head = head.next;
    }
    ListNode pre = head, curr = head.next;
    while (curr != null) {
        // 每次删除 curr
        if (curr.val == val) {
            pre.next = curr.next;
        } else {
            pre = curr;
        }
        curr = curr.next;
    }
    return head;
}

这样排版更加清晰，保留了原来的代码结构，同时使其更易于阅读。

80 - 简述 Java 实现无序链表删除重复节点

思路一：

遍历链表，把遍历的值存储到一个 Hashtable 中，在遍历过程中，若当前访问的值在 Hashtable 中已经存在，则说明这个数据是重复的，因此就可以删除。

  • 优点：时间复杂度较低 O(n)
  • 缺点：在遍历过程中需要额外的存储空间来保存已遍历过的值

思路二：

对链表进行双重循环遍历，外循环正常遍历链表，假设外循环当前遍历的节点为 cur，内循环从 cur 开始遍历，若碰到与 cur 所指向节点值相同，则删除这个重复节点。

  • 优点：不需要额外的存储空间
  • 缺点：时间复杂度较高 O(n^2)
/**
 * 时间复杂度为 O(n^2)
 * @param head
 * @return
 */
public static ListNode removeDuplicateNodes(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode outer = head;
    // 外层循环
    while (outer != null) {
        ListNode inner = outer;
        while (inner != null) {
            // inner 下一个节点值等于 outer 值，则删除 inner 的下一个节点
            if (inner.next != null && inner.next.val == outer.val) {
                // 删除后 inner 不移动，否则出现连续重复时无法删掉子集
                inner.next = inner.next.next;
            } else {
                inner = inner.next;
            }
        }
        outer = outer.next;
    }
    return head;
}

/**
 * 时间复杂度为 O(n)
 * @param head
 * @return
 */
public static ListNode removeDuplicateNodesByHashMap(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode curr = head, pre = null;
    Set<Integer> map = new HashSet<>();
    while(curr != null) {
        if(map.contains(curr.val)) {
            // 删除 curr
            pre.next = curr.next;
            curr = curr.next;
        } else {
            map.add(curr.val);
            pre = curr;
            curr = curr.next;
        }
    }
    return head;
}

public static void main(String[] args) {
    ListNode head = ListNode.create(new int[]{6, 3, 4, 4, 4, 1, 3, 7, 2, 6});
    // ListNode newHead = removeDuplicateNodes(head);
    ListNode newHead = removeDuplicateNodesByHashMap(head);
    ListNode.print(newHead);
}

81 - 简述Java有序链表删除重复节点

public static ListNode removeDuplicateNodes(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode curr = head, post = head.next;
    while (post != null) {
        if (curr.val == post.val) {
            curr.next = curr.next.next;
            post = curr.next;
        } else {
            curr = post;
            post = post.next;
        }
    }
    return head;
}

public static void main(String[] args) {
    ListNode head = ListNode.create(new int[]{1, 1, 3, 4, 4, 4, 5, 5, 7, 8, 8});
    ListNode newHead = removeDuplicateNodes(head);
    ListNode.print(newHead);
}

82-简述Java实现判断链表是否为回文

方法一：时间复杂度为 O(n)，空间复杂度为 O(n)（n 个）

  1. 遍历结点，压栈
  2. 再遍历结点，比较每一个当前节点与出栈节点是否相同

方法二：时间复杂度为 O(n)，空间复杂度为 O(n)（n/2 个）

  1. 快慢指针遍历，得到中间节点指针（慢指针），将慢指针指向的元素压栈（中间节点不压栈）
  2. 从中间节点指针开始遍历，比较每一个当前节点与出栈节点是否相同
/**
 * 方法二：时间复杂度为 O(n)，空间复杂度为 O(n)（n/2 个）
 * 1）快慢指针遍历，得到中间节点指针（慢指针），将慢指针指向的元素压栈（中间节点不压栈）
 * 2）从中间节点指针开始遍历，比较每一个当前节点与出栈节点是否相同
 * 
 * @param head
 * @return
 */
public static boolean isPalindromeByHalfStack(ListNode head) {
    ListNode fast = head, slow = head;
    // 处理空链表和只有一个节点的链表
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }
    // stack 保存了左半部分的节点
    Stack<Integer> stack = new Stack<>();
    while (fast != null && fast.next != null) {
        stack.push(slow.val);
        fast = fast.next.next;
        slow = slow.next;
    }
    // 如果是奇数个元素(fast.next == null)，那么 slow 从右半部分开始
    // 如果是偶数个元素，那么 slow 从中间开始
    if (fast != null) {
        slow = slow.next;
    }
    while (slow != null) {
        if (slow.val != stack.pop()) {
            return false;
        }
        slow = slow.next;
    }
    return true;
}

方法三：时间复杂度为 O(n)，空间复杂度为 O(1)

  1. 快慢指针遍历，得到中间节点指针（慢指针），将右半部分做逆序
  2. 链表头尾指针分别向中间移动，比较节点值是否一致
  3. 将链表调整回来
/**
 * 方法三：时间复杂度为 O(n)，空间复杂度为 O(1)
 * 1）快慢指针遍历，得到中间节点指针（慢指针），将右半部分做逆序
 * 2）链表头尾指针分别向中间移动，比较节点值是否一致
 * 3）将链表调整回来
 * 
 * @param head
 * @return
 */
public static boolean isPalindromeByInversion(ListNode head) {
    ListNode fast = head, slow = head;
    // 处理空链表和只有一个节点的链表
    if (head == null) {
        return false;
    }
    if (head.next == null) {
        return true;
    }
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // 如果是奇数个元素(fast.next == null)，那么 slow 从右半部分开始
    // 如果是偶数个元素，那么 slow 从中间偏右开始
    if (fast != null) {
        slow = slow.next;
    }
    // 注意，逆序后 fast 未必是右半部分的头节点，因为可能为 null，以 inverse 返回的为准
    ListNode rightHead = inverse(slow);
    ListNode rightCurr = rightHead;
    ListNode leftCurr = head;
    while (rightCurr != null) {
        if (leftCurr.val != rightCurr.val) {
            return false;
        }
        leftCurr = leftCurr.next;
        rightCurr = rightCurr.next;
    }
    inverse(rightHead);
    return true;
}

private static ListNode inverse(ListNode head) {
    ListNode pre = null, curr = head, post = head.next;
    while (post != null) {
        curr.next = pre;
        pre = curr;
        curr = post;
        post = post.next;
    }
    curr.next = pre;
    return curr;
}

83-简述Java实现简单链表复制

/**
 * 单链表拷贝
 * @param head
 * @return
 */
public static ListNode clone(ListNode head) {
    ListNode newHead = null;
    ListNode newCurr = null;
    
    while(head != null) {
        if(newHead == null) {
            newCurr = newHead = new ListNode(head.val);
        } else {
            newCurr.next = new ListNode(head.val);
            newCurr = newCurr.next;
        }
        head = head.next;
    }
    return newHead;
}

84 - 简述 Java 编程实现复杂链表复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

  1. 遍历链表，拷贝每一个节点，接在原节点的后面，新节点的 random 指针为 null。
  2. 重新遍历链表，同时维护两个指针，一个指向原节点，一个指向同值的新节点，拷贝 random 指针。
  3. 将新旧节点分离开来。
/**
 * 复制复杂链表
 *
 * @param head 链表头节点
 * @return 复制后的链表头节点
 */
public static RandomListNode cloneComplexLinkedList(RandomListNode head) {
    RandomListNode curr = head;

    // 1) 拷贝每一个节点
    while (curr != null) {
        RandomListNode newNode = new RandomListNode(curr.label);
        newNode.next = curr.next;
        curr.next = newNode;
        curr = curr.next.next;
    }

    // 2) 设置 random 指针
    curr = head;
    RandomListNode newCurr;
    while (curr != null) {
        newCurr = curr.next;
        // 注意 random 是有空的情况
        newCurr.random = curr.random == null ? null : curr.random.next;
        curr = curr.next.next;
    }

    // 3) 拆开原链表和新链表
    curr = head;
    RandomListNode newHead = null;
    newCurr = null;
    while (curr != null) {
        if (newHead == null) {
            newCurr = newHead = curr.next;
        } else {
            newCurr.next = curr.next;
            newCurr = curr.next;
        }
        // 跳过新链表节点
        curr.next = curr.next.next;
        curr = curr.next;
    }

    return newHead;
}

以上是对面试题标题和内容的排版优化，未对代码做任何改动。

85-简述 Java 链表判环

/**
 * 快慢指针
 * 最优解使用快慢指针实现，快指针一次走两步，慢指针一次走一步，
 * 如果无环，那么快指针会发现下一个为 null 。
 * 如果有环，那么一定会在环中的某个节点相遇。相遇时，快指针重新指向头节点，
 * 快指针和慢指针以同样速度继续遍历，再次相遇的节点即为进入环的第一个节点。
 *
 * @param head
 * @return
 */
public static ListNode getLoopStart(ListNode head) {
    ListNode fast = head, slow = head;
    
    if (head == null || head.next == null) {
        return null;
    }

    // 至少有两个节点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (slow == fast) {
            break;
        }
    }

    // 相遇，有环
    if (fast == slow) {
        // fast 重新指向头节点
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        // 相遇，即为环开始的第一个节点
        return slow;
    } else {
        return null;
    }
}

86 - 简述 Java 实现无环单链表判交

/**
 * 链表相交：
 * 1 ）一旦两个链表相交，那么两个链表中的节点一定有相同地址。
 * 2 ）一旦两个链表相交，那么两个链表从相交节点开始到尾节点一定都是相同的节点。
 * 返回两个链表第一个相交节点
 * 先统计两个链表的长度，比如 M 和 N ，假设 M > N ，则让较长链表先走 M-N 步，
 * 然后让两个链表同步走，比较是否是同一个节点，如果相同则为第一个相交节点。
 *
 * @param headA
 * @param headB
 * @return
 */
public static ListNode getFirstIntersectNode(ListNode headA, ListNode headB) {
    ListNode currA = headA;
    int lenA = 1;
    while (currA.next != null) {
        lenA++;
        currA = currA.next;
    }
    // 此时 currA 指向第一个链表的尾节点
    ListNode currB = headB;
    int lenB = 1;
    while (currB.next != null) {
        lenB++;
        currB = currB.next;
    }
    // 一定不相交
    if (currA != currB) {
        return null;
    }
    currA = headA;
    currB = headB;
    if (lenA >= lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            currA = currA.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            currB = currB.next;
        }
    }
    while (currA != null) {
        if (currA == currB) {
            return currA;
        }
        currA = currA.next;
        currB = currB.next;
    }
    return null;
}

说明：

  • 链表相交：当两个链表相交时，它们从相交点到尾部的节点完全相同。
  • 通过比较两个链表的长度，调整较长链表的指针位置，使两个链表从同一起点开始同步遍历，查找第一个相交节点。

87-简述Java实现有环单链表判交

/**
 * tail 可能是 null ，也可能是两个链表的某个公共节点
 *
 * @param headA
 * @param headB
 * @param tail
 * @return
 */
public static ListNode getFirstIntersectNodeBefore(ListNode headA, ListNode headB, ListNode tail) {
    ListNode currA = headA;
    int lenA = 1;
    while (currA.next != tail) {
        lenA++;
        currA = currA.next;
    }
    // 此时 currA 指向第一个链表的 tail 的前一个节点
    ListNode currB = headB;
    int lenB = 1;
    while (currB.next != tail) {
        lenB++;
        currB = currB.next;
    }
    // 一定不相交
    if (currA != currB) {
        return null;
    }
    currA = headA;
    currB = headB;
    if (lenA >= lenB) {
        for (int i = 0; i < lenA - lenB; i++) {
            currA = currA.next;
        }
    } else {
        for (int i = 0; i < lenB - lenA; i++) {
            currB = currB.next;
        }
    }
    while (currA != tail) {
        if (currA == currB) {
            return currA;
        }
        currA = currA.next;
        currB = currB.next;
    }
    return null;
}

/**
 * 有环单链表判交
 * 要求时间复杂度为 O(M+N) ，空间复杂度为 O(1) 。
 * 1 ）分别找到两个链表的第一个入环节点 A 和 B 。
 * 2 ）如果 A==B ，说明一定相交，如果想找到第一个相交节点，
 * 可以采用同无环单链表判交一样的方法，
 * 只是停止遍历的条件从 node 为 null 变为 node 为 A/B 。
 * 3 ） A != B ，可以设置一个第一个链表的指针，从 A 出发遍历，
 * 如果途中没有遇到 B ，说明不相交，否则相交。相交的话可以将 A 或 B 作为第一个相交的节点。
 *
 * @param headA
 * @param headB
 * @return
 */
public static ListNode getFirstIntersectNodeOfCyclicLinkedList(ListNode headA, ListNode headB) {
    ListNode loopStartA = LinkedListLoopStart.getLoopStart(headA);
    ListNode loopStartB = LinkedListLoopStart.getLoopStart(headB);
    
    // 一定相交，但未必是入环第一个节点
    if (loopStartA == loopStartB) {
        ListNode firstIntersectNode = getFirstIntersectNodeBefore(headA, headB, loopStartA);
        return firstIntersectNode != null ? firstIntersectNode : loopStartA;
    } else {
        // 未必相交，第一个链表指针从 A 开始遍历，如果回到 A 时仍然没有遇到 B，则无环
        ListNode currA = loopStartA;
        do {
            if (currA == loopStartB) {
                return loopStartA;
            }
            currA = currA.next;
        } while (currA != loopStartA);
    }
    return null;
}

88 - 简述单链表判交（可能有环也可能无环）

统一几种情况：两个链表可能有环也可能无环

/**
* 统一几种情况：两个链表可能有环也可能无环
* @param headA
* @param headB
* @return
*/
public static ListNode getFirstIntersectNodeOfLinkedList(ListNode headA,
    ListNode headB) {
    ListNode loopStartA = LinkedListLoopStart.getLoopStart(headA);
    ListNode loopStartB = LinkedListLoopStart.getLoopStart(headB);
    
    // 都无环
    if (loopStartA == null && loopStartB == null) {
        return getFirstIntersectNodeOfAcyclicLinkedList(headA, headB);
    }
    
    // 都有环
    else if (loopStartA != null && loopStartB != null) {
        return getFirstIntersectNodeOfCyclicLinkedList(headA, headB);
    }
    
    // 一个有环，一个无环，一定不相交
    else {
        return null;
    }
}

89-简述Java实现约瑟夫问题

时间复杂度为 O(mn)，空间复杂度为 O(n)

public class JosephusLinkedListImpl {
    private Node head; // 指向一个没有头结点的循环链表

    // 传入总数
    public JosephusLinkedListImpl(int n) {
        initial(n);
    }

    // 构造长度为 n 的循环链表
    private void initial(int n) {
        head = new Node(1, null);
        Node tail = head;
        for (int i = 2; i <= n; i++) {
            Node newNode = new Node(i, null);
            tail.next = newNode;
            tail = newNode;
        }
        tail.next = head;
    }

    // 传入间隔，每隔 gap 个元素就出队
    public void go(int gap) {
        int count = 0;
        Node ptr = head;
        while (true) { // 当 ptr 指向最后一个结点时退出循环
            count++;
            if ((count + 1) % gap == 0) { // ptr 指向待删除的结点的前一个结点
                // 删除下一个结点
                ptr.next = ptr.next.next;
                // 删掉的也要计数
                count++;
            }
            ptr = ptr.next; // 向后移动
            if (ptr == ptr.next) {
                System.out.println(ptr.data);
                return;
            }
        }
    }

    private static class Node {
        int data;
        Node next;

        Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        JosephusLinkedListImpl jose = new JosephusLinkedListImpl(8);
        jose.go(3);
    }
}

90 - 简述 Java 实现合并两个有序链表

public static ListNode merge(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return headA != null ? headA : headB;
    }

    ListNode resultHead = null;
    ListNode resultTail = null;

    while (headA != null && headB != null) {
        if (headA.val <= headB.val) {
            if (resultHead == null) {
                resultTail = resultHead = headA;
            } else {
                resultTail.next = headA;
                resultTail = headA;
            }
            headA = headA.next;
        } else if (headA.val > headB.val) {
            if (resultHead == null) {
                resultTail = resultHead = headB;
            } else {
                resultTail.next = headB;
                resultTail = headB;
            }
            headB = headB.next;
        }
    }

    if (headA != null) {
        resultTail.next = headA;
    }

    if (headB != null) {
        resultTail.next = headB;
    }

    return resultHead;
}

91 - 简述 Java 单链表归并排序？

给单链表排序，时间复杂度 O(nlogn)，空间复杂度 O(1)

/**
 * 时间复杂度 O（nlogn），不考虑递归栈空间的话空间复杂度是 O（1）
 * @param head
 * @return
 */
public static ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    // fast 一定不为空
    ListNode secondHalf = slow.next;
    slow.next = null;
    // 前半段 head~slow
    ListNode firstHalf = mergeSort(head);
    // 后半段 slow.next ~ fast
    secondHalf = mergeSort(secondHalf);
    return merge(firstHalf, secondHalf);
}

private static ListNode merge(ListNode firstHalf, ListNode secondHalf) {
    if (firstHalf == null || secondHalf == null) {
        return firstHalf != null ? firstHalf : secondHalf;
    }
    ListNode head = null;
    ListNode tail = null;
    while (firstHalf != null && secondHalf != null) {
        if (firstHalf.val <= secondHalf.val) {
            if (head == null) {
                tail = head = firstHalf;
            } else {
                tail.next = firstHalf;
                tail = firstHalf;
            }
            firstHalf = firstHalf.next;
        } else {
            if (head == null) {
                tail = head = secondHalf;
            } else {
                tail.next = secondHalf;
                tail = secondHalf;
            }
            secondHalf = secondHalf.next;
        }
    }
    if (firstHalf != null) {
        tail.next = firstHalf;
    }
    if (secondHalf != null) {
        tail.next = secondHalf;
    }
    return head;
}

92 - 简述寻找数组中唯一出现奇数次数的元素（异或）

/**
* e 与 0 异或，得到 e
* e 与 1 异或，得到 e 取反值
* e 与 e 异或，得到全 0
*
* 因为异或满足交换律和结合律，可以视为出现偶数次的元素先进行了异或，得到了 0，
* 那么结果就是 e (值为 0) ^ 0 ^ 出现奇数次的元素
* 
* @param arr
* @return
*/
public static int get(int[] arr) {
    int e = 0;
    for (int i = 0; i < arr.length; i++) {
        e ^= arr[i];
    }
    return e;
}

93-简述Java寻找数组中唯二出现奇数次数的元素（异或）

public static int[] get(int[] arr) {
    int e = 0;
    for (int i = 0; i < arr.length; i++) {
        e ^= arr[i];
    }

    // 此时 e = a ^ b ;
    // 因为 a 和 b 不同，那么至少有一位不同，不同位异或，得到的是 1，
    // 所以 e 中肯定有一位是 1，假设第 k 位为 1

    // 第 k 位不同，所以 a 或者 b 中的某一个的第 k 位为 1，
    // 遍历数组找到该数
    int k = 1;
    while (((e >> k) & 1) != 1) {
        k++;
    }

    int e1 = 0;
    for (int i = 0; i < arr.length; i++) {
        if (((arr[i] >> k) & 1) == 1) {
            e1 ^= arr[i];
        }
    }

    // e1 等于 a 或者 等于 b
    // e2 等于 b 或者 等于 a
    int e2 = e ^ e1;
    int[] result = {Math.min(e1, e2), Math.max(e1, e2)};
    return result;
}

94-寻找乱序后的连续数字 [1, N] 中缺失的数字 / 数组中唯一的重复数字

题目描述：

一个连续的数字数组 [1, N] ，缺失了一个数，顺序也被打乱了。

解法：

  1. 哈希表
  2. 排序：比较相邻数字是否连续。
  3. 先求 1~N 的和，再减去数组的和：这种方式会存在溢出的风险。
  4. 1~N 取异或，结果再与数组每个值异或：结果即为缺失的数，且不会溢出。

代码实现：

public class Solution {

    // 通过求和来找缺失的数字
    public static int findMissing(int[] arr, int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        
        int arraySum = 0;
        for (int i = 0; i < arr.length; i++) {
            arraySum += arr[i];
        }
        
        return sum - arraySum;
    }

    // 通过异或来找缺失的数字
    public static int findMissingByXOR(int[] arr, int n) {
        if (arr == null || arr.length == 0 || n <= 0) {
            throw new IllegalArgumentException();
        }
        
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result ^= i;
        }
        
        for (int i = 0; i < arr.length; i++) {
            result ^= arr[i];
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 6, 1};
        System.out.println(findMissing(arr, 6));
    }
}

说明：

  • findMissing 方法使用的是求和方式，计算出 1 到 N 的和与数组元素和的差值，从而找到缺失的数字。
  • findMissingByXOR 方法利用异或特性，通过将 1 到 N 的所有数字和数组元素依次异或，最终的结果就是缺失的数字。
默认页脚
Copyright © 2025 江小北