1.1 什么是冒泡排序？如何优化？

冒泡排序算法原理：（从小到大排序）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，交换一趟后，最后的元素会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次，对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

优化方案1（定义一个变量 l 来保存一趟交换中两两交换的次数，如果 l == 0，则说明排序已经完成，退出for循环）

优化方案2（假如有一个长度为50的数组，在一趟交换后，最后发生交换的位置是10，那么这个位置之后的40个数必定已经有序了，记录下这位置，下一趟交换只要从数组头部到这个位置就可以了）

定义一个变量 n 来保存一趟交换中最后一次发生交换的位置，并把它传递给下一趟交换

1.2请用 Java 实现一个简单的单链表？

定义链表：

    public class ListNode {
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }

基本操作

    public class SingleLinkedList {
        /**
         * 链表的头结点
         */
        ListNode head = null;

        /**
         * 链表添加结点:
         * 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
         * @param data
         */
        public void addNode(int data) {
            ListNode newNode = new ListNode(data);
            if (head == null) {
                head = newNode;
                return;
            }
            ListNode temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }

        /**
         * 链表删除节点:
         * 把要删除结点的前节点指向要删除节点的后节点，即直接跳过待删除节点
         * @param index
         * @return
         */
        public boolean deleteNode(int index) {
            if (index < 1 || index > length()) {//待删除节点不存在
                return false;
            }
            if (index == 1) {//删除头节点
                head = head.next;
                return true;
            }
            ListNode preNode = head;
            ListNode curNode = preNode.next;
            int i = 1;
            while (curNode != null) {
                if (i == index) {//寻找到待删除节点
                    //待删除节点的前节点指向待删除节点的后节点
                    preNode.next = curNode.next;
                    return true;
                }
                //当前节点和前节点同时向后移
                preNode = preNode.next;
                curNode = curNode.next;
                i++;
            }
            return true;
        }

        /**
         * 求链表的长度
         * @return
         */
        public int length() {
            int length = 0;
            ListNode curNode = head;
            while (curNode != null) {
                length++;
                curNode = curNode.next;
            }
            return length;
        }

        /**
         * 打印结点
         */
        public void printLink() {
            ListNode curNode = head;
            while (curNode != null) {
                System.out.print(curNode.val + "");
                curNode = curNode.next;
            }
            System.out.println();
        }

        /**
         * 查找正数第k个元素
         */
        public ListNode findNode(int k) {
            if (k < 1 || k > length()) {//不合法的k
                return null;
            }
            ListNode temp = head;
            for (int i = 0; i < k - 1; i++) {
                temp = temp.next;
            }
            return temp;
        }

        public static void main(String[] args) {
            SingleLinkedList myLinkedList = new SingleLinkedList();
            //添加链表结点
            myLinkedList.addNode(9);
            myLinkedList.addNode(8);
            myLinkedList.addNode(6);
            myLinkedList.addNode(3);
            myLinkedList.addNode(5);
            //打印链表
            myLinkedList.printLink();
            System.out.println("链表节点个数为：" + myLinkedList.length());
            myLinkedList.deleteNode(3);
            myLinkedList.printLink();
        }
    }

1.3 如何反转一个单链表？

思路：定义3个节点分别是preNode, curNode, nextNode.
先将curNode的next赋值给nextNode, 再curNodel的next指向preNode.至此curNode的指针调整完毕。 然后往后移动curNode, 将curNode赋值给preNode，将nextNode赋值给curNode，如此循环到curNode==null为止

代码：

    public static Node reverseListNode(Node head) {
        //单链表为空或只有一个节点，直接返回原单链表
        if (head == null || head.getNext() == null) {
            return head;
        }
        //前一个节点指针
        Node preNode = null;
        //当前节点指针
        Node curNode = head;
        //下一个节点指针
        Node nextNode = null;
        ...
        while (curNode != null) {
            nextNode = curNode.getNext();//nextNode 指向下一个节点
            curNode.setNext(preNode);//将当前节点next域指向前一个节点
            preNode = curNode;//preNode 指针向后移动
            curNode = nextNode;//curNode指针向后移动
        }
        return preNode;
    }

1.4 谈谈你对时间复杂度和空间复杂度的理解？

在进行算法分析时，语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。

这样用大写 O()来体现算法时间复杂度的记法，我们称之为大O记法。随着 n 的增大，T(n) 增长最慢的算法为最优算法

算法的空间复杂度是通过计算算法所需的存储空间实现，记作：S(n) = O(f(n))，其中，n 为问题的规模，f(n) 为语句关于 n 所占存储空间的函数。

若算法执行时间所需要的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为 O(1)。

1.5 谈一谈如何判断一个链表成环？

Two ways to solve:
Two Pointers:

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null)
                return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

HashSet:

    public boolean hasCycle(ListNode head) {
        Set<ListNode> dict = new HashSet<>();
        while (head != null) {
            if (dict.contains(head)) {
                return true;
            } else {
                dict.add(head);
            }
            head = head.next;
        }
        return false;
    }

1.6 什么是红黑树？为什么要用红黑树？

java 的 HashMap, TreeMap, TreeSet, Linux 的虚拟内存管理;
了解红黑树之前, 先了解二叉搜索树:
1.. 左子树上所有结点的值均小于或等于它的根结点的值;
2.. 右子树上所有结点的值均大于或等于它的根结点的值;

但是这样的二叉树, 很有可能变成线性结构, 为了避免出现这样的情况, 产生了红黑树;
每个节点, 都包含5个属性：color, key, left, right 和parent;
如果一个节点没有子节点, 或者没有父节点, 则其对应属性值为 NULL;
我们可以把这些 NULL 视为指向二叉搜索树的叶子节点指针, 外部指针;
把带关键字的节点视为树的内部节点;

一般红黑树必须是满足以下属性的二叉搜索树:
1.. 每个节点是红色, 或者是黑色;
2.. 根节点是黑色;
3.. NULL 节点是黑色的;
4.. 如果一个节点是红色的, 那么他的两个子节点都是黑色的;
5.. 每个节点到所有叶子节点, 所经过的黑色节点数量相同;
6.. 最长路径不会超过最短路径的 2 倍;

从某个节点 N 出发, 达到一个叶子节点, 经过任意一个简单路径, 其黑色节点的个数称之为黑高, 记为 bh;
红黑树必须满足, 任意一个节点, 到其任意一个叶子节点, 经过任意的简单路径, 其黑高相等;

左旋传会带上左父亲, 右旋转会带上右父亲;

插入操作

基本描述
要将红黑树当作一棵二叉查找树, 找到插入的位置;
将节点着色为红色(默认就是红色);
通过旋转和重新着色, 对其修正, 使之成为一棵新的红黑树;
因为新插入的节点, 肯定是叶子节点, 所以要满足[每个节点到所有叶子节点, 所经过的黑色节点数量相同];
接下来, 还要依次满足剩余所有的基本属性;

什么情况下需要旋转, 什么情况下不需要旋转?
如果新插入的当前节点的父节点, 是黑色的, 就不需要做任何操作;
如果新插入的当前节点的父节点, 是红色的, 就需要重新着色, 旋转;
红黑树调整的整体思想是, 将红色的节点移到根节点, 然后,将根节点设为黑色;

调整红黑树
(1)当前节点是根节点, 直接设为黑色的;
(2)当前节点的父节点是黑色的, 无序任何操作;
(3)当前节点的父节点是红色的, 叔叔节点是红色的;
将父亲节点, 设为黑色;
将叔叔节点, 设为黑色;
将祖父节点, 设为红色;
将祖父节点, 设为新的当前节点, 继续判断;
(4)当前节点的父节点, 是红色的, 叔叔节点是 T.nil 节点或者是黑色的, 当前节点是父节点的右孩子;
将祖父节点设为红色;
将父节点设为黑色;
当前节点的父节点, 设为新的当前节点;
以当前节点, 为支点进行左旋, 继续判断;
(5)当前节点的父节点, 是红色的, 叔叔节点是 T.nil 节点或者是黑色的, 当前节点是父节点的左孩子;
将祖父节点设为红色;
将父节点设为黑色;
当前节点的父节点, 设为新的当前节点;
以当前节点, 为支点进行右旋, 继续判断;

删除操作

待删除的节点情况可以分为 3 种:
1.. 是叶子节点;
2.. 只有左子树或只有右子树;
3.. 有左子树和右子树;

调整红黑树
后继节点, 就是右子树上最小的节点;
前驱节点, 就是左子树上最大的节点;
先看待删除的节点的颜色, 再看兄弟节点的颜色, 先看远侄子再看近侄子, 最后看父亲节点的颜色;
case.. 待删除的节点, 是红色的, 没有子节点, 直接删除既可;
case.. 待删除的节点, 是红色的, 只有一个子节点, 子节点一定是黑色的, 父节点也一定是黑色的;
直接删除当前节点, 子节点替换当前节点, 设为黑色即可;
case.. 待删除的节点, 是红色的, 它有两个子树, 当然左右子树都是黑色的, 父节点是黑色的;
从待删除的右子树, 找到最小的节点;
待删除节点与右子树最小节点, 数值互换;
右子树最小节点作为新的待删除节点, 继续判断;
case.. 待删除的节点, 是黑色的, 只有一个子节点, 子节点是红色的;
直接删除当前节点, 子节点替换当前节点, 设为黑色即可;
case.. 待删除的节点, 是黑色的, 是父节点的左子树, 并且兄弟节点是红色的;
父节点和兄弟节点颜色互换, 以兄弟节点为支点, 左旋传, 继续判断;
case.. 待删除的节点, 是黑色的, 是父节点的左子树, 它的兄弟节点是黑色的, 远侄子是红色的;
父节点和兄弟节点颜色互换, 远侄子设为黑色, 删除当前节点, 以兄弟节点为支点, 左旋传即可;
case.. 待删除的节点, 是黑色的, 是父节点的左子树, 它的兄弟节点是黑色的, 近侄子是红色的;
兄弟节点和近侄子颜色互换, 以兄弟节点为支点, 右旋传, 继续判断;
case.. 待删除的节点, 是黑色的, 是父节点的左子树, 它的兄弟节点是黑色的, 两个侄子都是黑色的;
从待删除的右子树, 找到最小的节点;
待删除节点与右子树最小节点, 数值互换;
右子树最小节点作为新的待删除节点, 继续判断;
case.. 待删除的节点, 是黑色的, 是父节点的右子树, 并且兄弟节点是红色的;
父节点和兄弟节点颜色互换, 以兄弟节点为支点, 右旋传, 继续判断;
case.. 待删除的节点, 是黑色的, 是父节点的右子树, 它的兄弟节点是黑色的, 远侄子是红色的;
父节点和兄弟节点颜色互换, 远侄子设为黑色, 删除当前节点, 以兄弟节点为支点, 右旋转即可;
case.. 待删除的节点, 是黑色的, 是父节点的右子树, 它的兄弟节点是黑色的, 近侄子是红色的;
兄弟节点和近侄子颜色互换, 以兄弟节点为支点, 左旋传, 继续判断;
case.. 待删除的节点, 是黑色的, 是父节点的右子树, 它的兄弟节点是黑色的, 两个侄子都是黑色的;
从待删除的右子树, 找到最小的节点;
待删除节点与右子树最小节点, 数值互换;
右子树最小节点作为新的待删除节点, 继续判断;
case.. 待删除的节点, 是黑色的, 它的兄弟节点是黑色的, 它和兄弟节点都没有子节点;
父节点设为黑色, 兄弟节点设为红色, 删除当前节点即可;

1.7 什么是快速排序？如何优化？

快速排序是从冒泡排序演变而来的算法，但是其比冒泡排序要高效，所以叫做快速排序，简单理解如下。

我举个简单例子来理解吧：
比如我们即将排序的数组如下：

1 8 9 5 6 3 0
我们一般将首位 1 或者最后一个数字 0 认为是基准元素，然后左右对比，大致规律如下：
第一次 ： 将 1 移出，从最右边 数字0 开始，如果 <= 基准数1，则将其移到左边第一个位置，此时 最右边的数字相当于被挖空。
如下，其中 — 代表被挖空的数字
0 8 9 5 6 3 —
接下来从左边开始，如果大于等于基准数1，则将移到右边
刚才挖空的位置上，如下:
0 — 9 5 6 3 8
接下来继续从右边开始，刚才右边我们进行到3了，继续左移，如果遇到 <= 基准数 1，那么将其移到刚才 挖的 坑上，如果没有遇到，并且左右操作的数相同时，此时将基准数移动到这个空着的坑位。
如下：
0 1 9 5 6 3 8
我们可以发现，基准数1左边的都小于其，右边的都大于其，所以两边各自继续按照刚才上面的逻辑继续递归。(虽然这里最左边只是0，可以忽略)
接下来的过程如下：
0 1 — 5 6 3 8 (基准数9)

0 1 8 5 6 3 —

0 1 8 5 6 3 9
0 1 — 5 6 3 9 （基准数8）

0 1 3 5 6 9 _
0 1 3 5 6 _ 9

0 1 3 5 6 8 9 （基准数6）

优化：
快速排序在序列中元素很少时，效率将比较低，不如插入排序，按需使用。
基准数采用随机。
尾递归优化。
快速排序和分治排序算法一样，都有两次递归调用，而且快排的递归在尾部，所以我们可以对快排代码实施尾递归优化。减少堆栈深度。
将每次分割结束后，将于本次基数相等的元素聚集在一起，再次分割时，避免对聚集过的元素进行分割。
多线程优化，基于分治法的思想，将一个规模为 n 的问题分解为 k个规模较小的问题。这些子问题互相独立且与原问题相同。求解这些子问题，然后将子问题的解合并，从而得到原问题的解。

1.8 说说循环队列？

引用的前面设计的数组类 Array.java

    /**
     * Array
     */
    public class Array<E> {
        private E[] data;
        private int size;

        /**
         * 构造函数
         *
         * @param capacity 传入数值初始值大小
         */
        public Array(int capacity) {
            //Java不支持直接构造函数中new 泛型数据类型，使用强制装换
            // data = new E[capacity];
            data = (E[]) new Object[capacity];
            size = 0;
        }

        /**
         * 无参构造函数，默认容量capacity=10
         */
        public Array() {
            this(10);
        }

        /**
         * @return 返回数组元素的个数
         */
        public int getSize() {
            return size;
        }

        /**
         * @return 返回数组的容量
         */
        public int getCapacity() {
            return data.length;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 向数组中添加一个元素
         *
         * @param e
         */
        public void addLast(E e) {
            add(size, e);
        }

        /**
         * 向数组添加一个 元素
         *
         * @param e
         */
        public void addFirst(E e) {
            add(0, e);
        }

        /**
         * 在index位置插入一个元素
         *
         * @param index 位置
         * @param e     参数值
         */
        public void add(int index, E e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("AddList failed.Require index>=0 and index <= size");
            }
            if (size == data.length) {
                resize(2 * data.length);
            }
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }

        /**
         * 获取数组中某一元素
         *
         * @param index
         * @return
         */
        public E get(int index) {
            if (index < 0 || index >= size) {
                throw new
                        IllegalArgumentException("Get failed.Index is illegal.");
            }
            return data[index];
        }

        public E getLast() {
            return get(size - 1);
        }

        public E getFirst() {
            return get(0);
        }

        /**
         * 设置某一位置的元素值
         *
         * @param index
         * @param e
         */
        public void set(int index, E e) {
            if (index < 0 || index >= size) {
                throw new
                        IllegalArgumentException("Get failed.Index is illegal.");
            }
            data[index] = e;
        }

        /**
         * 查找数组中是否包含某一元素e
         *
         * @return
         */
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)) {
                    return true;
                }
            }
            return false;
        }

        /**
         * 查找数组中元素e的位置
         *
         * @param e 查找元素
         * @return 成功返回元素下标，不成功返回-1
         */
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                //比较是否为同一对象
                if (data[i].equals(e)) {
                    return i;
                }
            }
            return -1;
        }

        /**
         * 删除index位置的元素，返回index中的元素
         *
         * @param index
         * @return
         */
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new
                        IllegalArgumentException("Get failed.Index is illegal.");
            }
            E res = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size--;
            data[size] = null; //loitering object != memory leak
            //减少容量，不能创建数组大小为0
            if (size == data.length / 4 &&
                    data.length / 2 != 0) {
                resize(data.length / 2);
            }
            return res;
        }

        /**
         * 删除数组首元素
         *
         * @return
         */
        public E removeFirst() {
            return remove(0);
        }

        /**
         * 删除数组末尾元素
         */
        public E removeLast() {
            return remove(size - 1);
        }

        /**
         * 删除数组中指定元素
         *
         * @param e
         * @return
         */
        public boolean removeElement(E e) {
            int index = find(e);
            if (index != -1) {
                remove(index);
                return true;
            }
            return false;
        }

        /**
         * @return 返回数组大小、容量
         */
        @Override
        public String toString() {
            StringBuilder res = new
                    StringBuilder();
            res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
            res.append('[');
            for (int i = 0; i < size; i++) {
                res.append(data[i]);
                if (i != size - 1) {
                    res.append(", ");
                }
            }
            res.append(']');
            return res.toString();
        }

        /**
         * 数组扩容
         *
         * @param newCapacity
         */
        private void resize(int newCapacity) {
            E[] newData = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newData[i] = data[i];
            }
            data = newData;
        }
    }

定义队列的接口 Queue.java

    /**
     * Queue
     */
    public interface Queue<E> {
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

普通队列 ArrayQueue.java

    /**
     * ArrayQueue
     *
     */
    public class ArrayQueue<E> implements Queue<E> {
        private Array<E> array;

        public ArrayQueue(int capacity) {
            array = new Array<>(capacity);
        }

        public ArrayQueue() {
            array = new Array<>();
        }

        @Override
        public int getSize() {
            return array.getSize();
        }

        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }

        public int getCapacity() {
            return array.getCapacity();
        }

        /**
         * 添加元素
         */
        @Override
        public void enqueue(E e) {
            array.addLast(e);
        }

        /**
         * 取出元素
         *
         * @return
         */
        @Override
        public E dequeue() {
            return array.removeFirst();
        }

        /**
         * 查看队首元素
         *
         * @return
         */
        @Override
        public E getFront() {
            return array.getFirst();
        }

        @Override
        public String toString() {
            StringBuilder res = new
                    StringBuilder();
            res.append("Queue: ");
            res.append("front [");
            for (int i = 0; i < array.getSize();
                 i++) {
                res.append(array.get(i));
                if (i != array.getSize() - 1) {
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    }

循环队列 LoopQueue.java

    /**
     * LoopQueue
     */
    public class LoopQueue<E> implements Queue<E> {
        private E[] data; //数组
        private int front; //队头
        private int tail; //队尾
        private int size; //容量

        public LoopQueue(int capacity) {
            data = (E[]) new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }

        public LoopQueue() {
            this(10);
        }

        /**
         * 容量
         *
         * @return
         */
        public int getCapacity() {
            return data.length - 1;
        }

        @Override
        public int getSize() {
            return size;
        }

        @Override
        public boolean isEmpty() {
            return front == tail;
        }

        /**
         * 入队
         *
         * @param e
         */
        @Override
        public void enqueue(E e) {
            if ((tail + 1) % data.length == front) {
                resize(getCapacity() * 2);
            }
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size++;
        }

        /**
         * 出队
         *
         * @return
         */
        @Override
        public E dequeue() {
            if (isEmpty()) {
                throw new
                        IllegalArgumentException("Cannot dequeue from an queue.");
            }
            E ret = data[front];
            data[front] = null;
            front = (front + 1) % data.length;
            size--;
            if (size == getCapacity() / 4 &&
                    getCapacity() / 2 != 0) {
                resize(getCapacity() / 2);
            }
            return ret;
        }

        /**
         * 获取队头元素
         *
         * @return
         */
        @Override
        public E getFront() {
            if (isEmpty()) {
                throw new IllegalArgumentException("Queue is empty.");
            }
            return data[front];
        }

        /***
         * 队列扩容或缩减
         * @param newCapacity 扩容或缩减大小
         */
        private void resize(int newCapacity) {
            E[] newData = (E[]) new Object[newCapacity + 1];
            for (int i = 0; i < size; i++) {
                newData[i] = data[(i + front % data.length)];
            }
            data = newData;
            front = 0;
            tail = size;
        }

        @Override
        public String toString() {
            StringBuilder res = new
                    StringBuilder();
            res.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapacity()));
            res.append("front [");
            for (int i = front; i != tail; i = (i + 1) % data.length) {
                res.append(data[i]);
                if ((i + 1) % data.length != tail) {
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }

        public static void main(String[] args) {
            LoopQueue<Integer> queue = new
                    LoopQueue<>();
            for (int i = 0; i < 10; i++) {
                queue.enqueue(i);
                System.out.println(queue);
                if (i % 3 == 2) {
                    queue.dequeue();
                    System.out.println(queue);
                }
                System.out.println("---");
            }
        }
    }

队列的运行比较 Main.java

    public class Main {
        private static double testQueue(Queue<Integer> q, int opCount) {
            long startTime = System.nanoTime();
            Random random = new Random();
            for (int i = 0; i < opCount; i++) {
                q.enqueue(random.nextInt(Integer.MAX_VALUE));
            }
            for (int i = 0; i < opCount; i++) {
                q.dequeue();
            }
            long endTime = System.nanoTime();
            return (endTime - startTime) /
                    1000000000.0;
        }

        public static void main(String[] args) {
            int opCount = 100000;
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
            double time1 = testQueue(arrayQueue, opCount);
            System.out.println("ArrayQueue, time: " + time1 + "s");
            LoopQueue<Integer> loopQueue = new LoopQueue<>();
            double time2 = testQueue(loopQueue, opCount);
            System.out.println("LoopQueue, time: " + time2 + "s");
        }
    }

1.9 如何判断单链表交叉

这个题应该是问假如两个单键表相交，请找出相交的位置的节点。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ```
        ListNode currA = headA;
        ListNode currB = headB;
        int lengthA = 0;
        int lengthB = 0;
        // 让长的先走到剩余长度和短的一样
        while (currA != null) {
            currA = currA.next;
            lengthA++;
        }
        while (currB != null) {
            currB = currB.next;
            lengthB++;
        }
        currA = headA;
        currB = headB;
        while (lengthA > lengthB) {
            currA = currA.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            currB = currB.next;
            lengthB--;
        }
        // 然后同时走到第一个相同的地方
        while (currA != currB) {
            currA = currA.next;
            currB = currB.next;
        }
        // 返回交叉开始的节点
        return currA;
        ```
    }