牛客网面试必刷TOP101

刷题必看

题目链接：https://www.nowcoder.com/exam/oj
配套详解：https://uploadfiles.nowcoder.com/bm/top101.html

专题1：链表

BM1 反转链表

方法1：迭代
单链表就是每个结点有一个值，还有一个next 指针指向下一个结点，尾结点指向特殊位置null。解决链表问题，就是顺藤摸瓜，可以从前往后依次处理。
要反转单链表，首先准备两个指针pre 和 cur，分别指向前一个结点和当前结点，每次先保存当前结点的next 结点，然后修改当前结点的指向，再同步移动pre 和 cur 指针，等到当前结点为空，此时pre 走到原链表的尾结点，而它此时又是反转后链表的头结点，返回它即可。

public class Solution {
    // 方法1：迭代
    public ListNode ReverseList(ListNode head) {
        // 1. 处理参数
        if (head == null) {
            return null;
        }
        // 2. 准备两个指针，pre 指向上一个结点，cur 指向当前结点
        ListNode pre = null;
        ListNode cur = head;
        // 3. 从头结点往后遍历，顺藤摸瓜，依次处理
        while (cur != null) {
            // 4. 反转操作会使链表断开，所以先用变量记录下一个结点
            ListNode curNext = cur.next;
            // 5. 反转当前结点的next指向
            cur.next = pre;
            // 6. 同步移动两个指针，
            pre = cur;
            cur = curNext;
        }
        // 7. 返回反转后的头结点，即pre最后所指的结点
        return pre;
    }
}

方法2：递归。
从迭代方法中可以看到，当从前往后遍历，反转一个节点的next 指向后，要进入下一个结点再次进行反转，相当于对规模小一级的子链表进行反转，这就是一个子问题，因此可以使用递归。

递归的模板：终止条件、返回值、本级处理。
终止条件：当前结点为空，或是尾结点，返回当前结点对象
返回值：本题把反转后的尾结点，通过各层调用向上返回。
本级处理：对当前结点的下一个进行处理，在本层调用中，把下一个结点的next 修改为指向当前结点，再把当前结点的next 指向null。

递归调用的执行过程示意图：要多想想整个执行流程，深刻理解递归。

// 方法2：递归（从后往前反转）
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 1. 递归的终止条件
        if (head == null || head.next == null) {
            // 终止时刻的返回值
            return head;
        }
        // 2. 递归调用：得到反转后的头结点
        ListNode newHead = ReverseList(head.next);
        // 3. 本级处理：反转当前结点的指向
        ListNode curNext = head.next;
        curNext.next = head;
        head.next = null;
        // 4. 中间层：把反转后的头结点层层向上返回
        return newHead;
    }
}

方法3：尾递归。
题解里面有人解释：https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=295&tqId=23286&ru=%2Fpractice%2F886370fe658f41b498d40fb34ae76ff9&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj

这种递归往下传递的时候基本上没有逻辑处理，当往回反弹的时候才开始处理，也就是从链表的尾端往前开始处理的。我们还可以再来改一下，在链表递归的时候从前往后处理，处理完之后直接返回递归的结果，这就是所谓的尾递归，不过线上测试显示时间差不多。

// 方法3：尾递归（从前往后，先反转处理再递归）
public class Solution {
    public ListNode ReverseList(ListNode head) {
        return reverseFromHead(head, null);
    }
    private ListNode reverseFromHead(ListNode head, ListNode newHead) {
        // 1. 递归的终止条件：
        if (head == null) {
            return newHead;
        }
        // 2. 本级处理：记录下一个结点，并且修改当前结点的指向
        ListNode curNext = head.next;
        head.next = newHead;
        // 3. 处理后进行递归调用
        return reverseFromHead(curNext, head);
    }
}

BM2 反转链表某段区间

描述
将一个 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)

方法1：迭代-头插法
链表问题创建一个虚拟头结点，避免对头结点复杂的情况进行分类讨论，简化操作。

算法流程：
要找到第m个位置才能开始反转链表，而反转的部分就是从第m个位置到第n个位置。

• step 1：在链表前加一个表头，后续返回时去掉就好了，因为如果要从链表头的位置反转，也很方便。
• step 2：使用两个指针，cur 指向当前节点，pre 指向前序节点，也就是区间外，起到一个锚点的作用，用来每次对后面反转部分进行链接
• step 3：依次遍历链表，到第m个的位置。
• step 4：对于从m到n这些个位置的节点，依次修改当前结点指向，让它从指向后续结点temp，修改为指向隔一个的结点，然后把后序结点的指针修改为区间外pre 结点下一个结点，最后更新pre ，让pre 结点直接指向temp。
• step 5：返回时去掉我们添加的表头。

2022.05.19 昨天看着参考解释，感觉很简单，今天早上吃完早饭，自己试着写却写不出来。比较考验动态想象能力，画图会清晰很多。
2022.06.01 写不出来反转的代码
2022.06.16. 再次看代码，依然很懵，结合画图看了两三遍才想明白。

// 方法1：迭代法
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode anchor = dummy;
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            anchor = cur;
            cur = cur.next;
        }
        for (int i = m; i < n; i++) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = anchor.next;
            anchor.next = curNext;
        }
        return dummy.next;
    }
}

方法2：递归
具体做法：
我们来看看另一种分析：如果m == 1，就相当于反转链表的前n 元素；如果 m != 1我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转，如果把 head.next 的索引视为1，那相对于 head.next的反转的区间应该是从第 m - 1 个元素开始的，以此类推，反转区间的起点往后就是子问题，我们可以使用递归处理：

• 终止条件： 当m == 1，就可以直接反转前n个元素。
• 返回值： 将已经反转后的子问题头节点返回给上一级。
• 本级任务： 递归地缩短区间，进入子问题反转。

而每次反转，如果n == 1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），因此反转过程也可以使用递归：

• 终止条件： 当n == 1时，只反转当前头节点即可。
• 返回值： 将子问题反转后的节点头返回。
• 本级任务： 缩短n 进入子问题反转，并将当前节点接在反转后子问题的后面。

具体步骤如下：

• step 1：按照第一个递归的思路缩短子问题找到反转区间的起点。
• step 2：按照第二个递归的思路缩短终点的子问题，从第n 个位置开始反转，往上拼接。

这个流程图是指反转链表前3个结点：

// 方法2：递归
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 1. 递归的终止条件：找到子区间的头结点
        if (m == 1) {
            return reverse(head, n);
        }
        // 2. 递归调用，得到区间反转后的头结点
        ListNode newHead = reverseBetween(head.next, m - 1, n - 1);
        // 3. 修改当前结点的next 指向，连接反转区间
        head.next = newHead;
        // 4. 返回这一段的头结点，此时 head--> newHead
        return head;
    }
    // 变量anchor 起到一个锚定的作用，它始终指向区间右侧外的结点
    ListNode anchor = null;
    public ListNode reverse(ListNode head, int n) {
        if (n == 1) {
            anchor = head.next;
            return head;
        }
        ListNode newHead = reverse(head.next, n - 1);
        ListNode curNext = head.next;
        curNext.next = head;
        head.next = anchor;
        return newHead;
    }
}

BM3 链表k个结点为一组进行反转

方法1：递归。
这道题其实是BM1 和BM2 综合在一起的。
解题思路：首先，我们可以实现一个反转整个链表的方法，即问题BM1。

反转以head 为头结点的链表，其实就是反转[head, null）之间的结点，那么反转[start，end) 之间的结点，是不是只需要把null 改成 end？

具体做法：

• step 1：现在我们想一想，如果拿到一个链表，想要像上述一样分组翻转应该做些什么？首先肯定是分段吧，至少我们要先分成一组一组，才能够在组内翻转。分组很容易，只要每次遍历k个元素，就是一组。
• step 2：然后是组内翻转，翻转完了再连接起来。翻转即指定区间内的翻转，也很容易，可以参考链表指定区间内的翻转。
• step 3：最后是将反转后的分组连接，但是连接的时候遇到问题了：首先如果能够翻转，链表第一个元素一定是第一组，它翻转之后就跑到后面去了，而第一组的末尾元素才是新的链表首，我们要返回的也是这个元素，而原本的链表首要连接下一组翻转后的头部，即翻转前的尾部，如果不建立新的链表，看起来就会非常难。
• step 4：如果我们从最后的一个组开始翻转，得到了最后一个组的链表首，是不是可以直接连在倒数第二个组翻转后的尾（即翻转前的头）后面，是不是看起来就容易多了。

怎样从后往前呢？我们这时候可以用到自上而下再自下而上的递归或者说栈。接下来我们说说为什么能用递归？如果这个链表有n 个分组可以翻转，我们首先对第一个分组翻转，那么是不是接下来将剩余个n - 1分组翻转后的结果接在第一组后面就行了，那这剩余的n - 1 组就是一个子问题。我们来看看递归的三段式模版：

• 终止条件： 当进行到最后一个分组，即不足k 次遍历到链表尾（0次也算），就将剩余的部分直接返回。
• 返回值： 每一级要返回的就是翻转后的这一分组的头，以及连接好它后面所有翻转好的分组链表。
• 本级任务： 对于每个子问题，先遍历k次，找到该组结尾在哪里，然后从这一组开头遍历到结尾，依次翻转，结尾就可以作为下一个分组的开头，而先前指向开头的元素已经跑到了这一分组的最后，可以用它来连接它后面的子问题，即后面分组的头。

现在已经实现了反转链表某个区间的功能，那么只需要在遍历链表的过程中，将符合条件的区间进行反转，就可以解决问题了。思路说起来简单，但是代码中每次递归调用的流程轨迹很难想的透彻，一会儿懂，过一会儿又不明白了。

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 找到要反转的区间[head, end)
        ListNode end = head;
        for (int i = 0; i < k; i++) {
            if (end == null) {
                return head;
            }
            end = end.next;
        }
        // 2. 对[head, end) 区间进行反转，返回反转后的头结点
        ListNode newHead = reverseBetween(head, end);
        // 3. 递归，依次连接下一段链表
        head.next = reverseKGroup(end, k);
        // 4. 向上返回当前区间的头结点
        return newHead;
    }
    // 方法1：迭代
    // 对区间[start, end) 的链表进行反转
    private ListNode reverseBetween(ListNode head, ListNode end) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != end) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
    // // 方法2：递归。
    // // 对区间[start, end) 的链表进行反转，返回反转后的头结点。即BM2问题
    // private ListNode reverseBetween(ListNode head, ListNode end) {
    //     if (head.next == end) {
    //         return head;
    //     }
    //
    //     ListNode curNext = head.next;
    //
    //     ListNode newHead = reverseBetween(head.next, end);
    //
    //     curNext.next = head;
    //     head.next = null;
    //
    //     return newHead;
    // }
}

BM4 合并两个排序的链表

方法1：迭代
具体做法：
既然两个链表已经是排好序的，都是从小到大的顺序，那我们要将其组合，可以使用归并排序的思想：每次比较两个头部，从中取出最小的元素，然后依次往后。这样就能最快速地将最小的元素依次取出来排好序。

• step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
• step 2：新建一个空的表头后面连接两个链表排序后的结点。
• step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
• step 4：遍历到最后肯定有一个链表还有剩余的结点，它们的值将大于前面所有的，直接连在新的链表后面即可。

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        // 1. 为空直接返回另一个就行了
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // 2. 创建虚拟头结点和三个指针
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        ListNode p1 = list1;
        ListNode p2 = list2;
        // 3. 遍历两个链表，比较后进行合并
        while (p1 != null && p2 != null) {
            // 3.1 比较大小并修改指向关系
            if (p1.val <= p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        if (p1 != null) {
            cur.next = p1;
        } else {
            cur.next = p2;
        }
        return dummyHead.next;
    }
}

方法2：递归
上述方法中，我们利用归并思想不断合并两个链表，每当我们添加完一个节点后，该节点指针后移，相当于这个链表剩余部分与另一个链表剩余部分合并，两个链表剩余部分合并就是原问题两个有序链表合并的子问题，因此也可以使用递归。

• step 1：每次比较两个链表当前结点的值，然后取较小值的链表指针往后，另一个不变送入递归中。
• step 2：递归回来的结果我们要加在当前较小值的结点后面，相当于不断在较小值后面添加结点。

• step 3：递归的终止是两个链表为空。

  public class Solution {
    // 方法2：递归
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
  }

BM5. 合并k个已排序的链表

题目的主要信息：

• 给定k个排好序的升序链表
• 将这k个链表合并成一个大的升序链表，并返回这个升序链表的头

方法一：归并排序思想（推荐使用）
具体做法：
如果是两个有序链表合并，我们可能会利用归并排序合并阶段的思想：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。
其实这道题我们也可以两两比较啊，只要遍历链表数组，取出开头的两个链表，按照上述思路合并，然后新链表再与后一个继续合并，如此循环，知道全部合并完成。但是，这样太浪费时间了。
既然都是归并排序的思想了，那我们可不可以直接归并的分治来做，而不是顺序遍历合并链表呢？答案是可以的！
归并排序是什么？简单来说就是将一个数组每次划分成等长的两部分，对两部分进行排序即是子问题。对子问题继续划分，直到子问题只有1个元素。还原的时候呢，将每个子问题和它相邻的另一个子问题利用上述双指针的方式，1个与1个合并成2个，2个与2个合并成4个，因为这每个单独的子问题合并好的都是有序的，直到合并成原本长度的数组。

• step 1：对于这k个链表，就相当于上述合并阶段的k个子问题，需要两个合并，不断往上，最终合并成完整的一个链表。
• step 2：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半。

• step 3：将这两半子问题合并好了就成了两个有序链表，最后将这两个有序链表合并就成了，依据子问题递归处理。

• 终止条件： 划分的时候直到左右区间相等或左边大于右边。

• 返回值： 每级返回已经合并好的子问题链表。
• 本级任务： 对半划分，将划分后的子问题合并成新的链表。

注意：这道题划分左右边界的时候，一个是mid，另一个是mid + 1。
还有这句代码“int mid = left + (( right - left ) >> 1);”，必须要加括号，因为Java中 +- 的优先级比>> 高，不加括号代码意思就变了，会出错的。

public class Solution {
    // 方法1：归并排序思想
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return divide(lists, 0, lists.size() - 1);
    }
    // 1. 分治，对问题进行划分，直到只有一个元素
    private ListNode divide(ArrayList<ListNode> lists, int left, int right) {
        if (left > right) {
            return null;
        } else if (left == right) {
            return lists.get(left);
        }
        int mid = left + ((right - left) >> 1);
        ListNode nodeLeft = divide(lists, left, mid);
        ListNode nodeRight = divide(lists, mid + 1, right);
        // 2. 合并。1-->2-->4-->8...
        return merge(nodeLeft, nodeRight);
    }
    // 合并两个有序链表
    private ListNode merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 != null) {
            cur.next = list1;
        } else {
            cur.next = list2;
        }
        return dummyHead.next;
    }
}

方法二：优先队列（扩展思路）
我们也可以准备k个指针，每次比较得出k个数字中的最小值。利用Java提供的PriorityQueue或者C++ssSLT提供的优先队列，它是一种参照堆排序的容器，容器中的元素是有序的，如果是小顶堆，顶部元素就是最小的，每次可以直接取出最小的元素，而每次插入的成本根据堆排序，就是O(log2^N) 。也就是每次该容器中有k个元素，我们可以直接拿出最小的元素，再插入下一个元素，相当于每次都是链表的k个指针在比较大小。

• step 1：不管是Java 还是C++都需要重载比较方法，构造一个比较链表节点大小的小顶堆。
• step 2：先遍历k 个链表头，将不是空节点的节点加入优先队列。
• step 3：每次依次弹出优先队列中的最小元素，将其连接在合并后的链表后面，然后将这个节点在原本链表中的后一个节点（如果不为空的话）加入队列，类似上述双指针的过程。

PriorityQueue 是Java 提供的一个优先级队列类，其实就是堆结构，默认是小根堆。对Java 的基本数据类型，它已经定义好了排序规则，而对于其他类型，需要手动传入比较规则。这里 new PriorityQueue<>() 小括号中传入的参数是比较器，用流式编程定义了 ListNode 类比较排序的规则。

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> heap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null) {
                heap.add(lists.get(i));
            }
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (!heap.isEmpty()) {
            ListNode temp = heap.poll();
            cur.next = temp;
            cur = cur.next;
            if (temp.next != null) {
                heap.add(temp.next);
            }
        }
        return dummyHead.next;
    }
}

BM6 判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

方法1：快慢指针。
我们都知道链表不像二叉树，每个节点只有一个val 值和一个next 指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那这时我们就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。进入环中后，没有任何一个节点可以指针指出环，它们只能在环内不断循环，因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。
但是，环形链表遍历过程中会不断循环，线形链表遍历到NULL结束了，但是环形链表何时能结束呢？我们可以用一种双指针技巧，这也是处理环形链表常用的技巧：

• step 1：设置快慢两个指针，初始都指向链表头。
• step 2：遍历链表，快指针每次走两步，慢指针每次走一步。
• step 3：如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。

• step 4：如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。

  public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        // 必须判断fast 是否为空，不加这一句，当fast为空，访问它的next就会出现数组越界异常
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
  }

BM7 链表中环的入口结点

直觉好像是这样的：当慢指针刚进环，在跑完一圈前，一定会和快指针相遇，可惜不会证明。
不严谨的证明：假设慢指针到达环的入口处，此时快指针在环内某一点，距离入口为x，当慢指针跑完一圈，因为快指针速度是慢指针的2 倍，所以快指针跑完了2 圈，比慢指针多跑了一圈，这一圈的长度肯定比x 大，所以在慢指针跑完一圈之前，快指针一定能追上它，在某个位置相遇。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        // 1. 判断是否有环
        ListNode slow = hasCycle(pHead);
        if (slow == null) {
            return null;
        }
        // 2. 如果有环，快指针回到头结点，会在环入口处相遇
        ListNode fast = pHead;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    private ListNode hasCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }
}

BM8 链表中倒数第k个结点

方法1：快慢指针。
我们无法逆序遍历链表，就很难得到链表的倒数第k 个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第k 的位置上，即距离链表尾的距离是k，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是k 。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施：

• step 1：准备一个快指针，从链表头开始，在链表上先走k 步。
• step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是k 。

• step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数k 个元素的位置。

  public class Solution {
    public ListNode FindKthToTail(ListNode pHead, int k) {
        if (pHead == null) {
            return null;
        }
        ListNode slow = pHead;
        ListNode fast = pHead;
        for (int i = 0; i < k; i++) {
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
  }

BM9 删除链表的倒数第n个节点

方法1：双指针。
我们无法逆序遍历链表，就很难得到链表的倒数第n 个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第n 的位置上，即距离链表尾的距离是n，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是n。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施：

• step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
• step 2：准备一个快指针，在链表上先走n步。
• step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是n。
• step 4：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数第n 个元素的位置。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            if (fast == null) {
                return null;
            }
            fast = fast.next;
        }
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre.next = slow.next;
        return dummy.next;
    }
}

BM10. 两个链表的第一个公共结点

方法一：长度比较法（推荐使用）
具体做法：
如果两个链表有公共节点，那么它们后半部分都是相同的，我们要找的也就是后半部分的第一个节点，只要遍历两个指针同时抵达第一个相同的节点，我们就找到了它。

• step 1：单独的遍历两个链表，得到各自的长度。
• step 2：求得两链表的长度差，其中较长的链表的指针从头先走步。

• step 3：两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共结点；如果没有共同结点，那么两个指针都会指向最后的null，任意返回一个即可。

  // 方法1：长度比较法
  public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = getLength(pHead1);
        int len2 = getLength(pHead2);
        if (len1 > len2) {
            int count = len1 - len2;
            while (count != 0) {
                pHead1 = pHead1.next;
                count--;
            }
        } else {
            int count = len2 - len1;
            while (count != 0) {
                pHead2 = pHead2.next;
                count--;
            }
        }
        while (pHead1 != null && pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
    private int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
  }

方法2：交错走一遍。
具体做法：
由上种方法长度差的思路，不同上述一个指针先走另一个指针后走，仅需将两个链表连在一起，两个指针同步走。易知将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了两个链表，因此也是相同的，所以绕了一圈，第一个相同的结点便是第一个公共结点。

• step 1：判断链表情况，其中有一个为空，则不能有公共结点，返回null。
• step 2：两个链表都从表头开始同步依次遍历。
• step 3：不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。
• step 4：根据上述说法，第一个相同的结点便是第一个公共结点。

要多写写代码，因为看着简单，有些细节却很容易出错！
要多写写代码，因为看着简单，有些细节却很容易出错！
要多写写代码，因为看着简单，有些细节却很容易出错！

// 方法2：交错走一遍
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        // 必须新建这两个指针变量，用来遍历
        ListNode p1 =pHead1;
        ListNode p2 =pHead2;
        while (p1 != p2) {
            p1 = p1 == null ? pHead2 : p1.next;
            p2 = p2 == null ? pHead1 : p2.next;
        }
        return p1;
    }
}

BM11. 两个链表生成相加链表

方法：两次反转链表法（推荐使用）
具体做法：
既然链表每个节点表示数字的每一位，那相加的时候自然可以按照加法法则，从后往前依次相加。但是，链表是没有办法逆序访问的，这是我们要面对第一只拦路虎。解决它也很简单，既然从后往前不行，那从前往后总是可行的吧，将两个链表反转一下，即可得到个十百千……各个数字从前往后的排列，相加结果也是个位在前，怎么办？再次反转，结果不就正常了。

• step 1：任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
• step 2：相继反转两个待相加的链表，反转过程可以参考反转链表。
• step 3：设置返回链表的链表头，设置进位carry=0.
• step 4：从头开始遍历两个链表，直到两个链表节点都为空且carry也不为1. 每次取出不为空的链表节点值，为空就设置为0，将两个数字与carry相加，然后查看是否进位，将进位后的结果（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历。
• step 5：返回前将结果链表再反转回来。

public class Solution {
    public ListNode addInList(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode p1 = reverseList(head1);
        ListNode p2 = reverseList(head2);
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        while (p1 != null || p2 != null || carry != 0) {
            int plus1 = p1 == null ? 0 : p1.val;
            int plus2 = p2 == null ? 0 : p2.val;
            int sum = plus1 + plus2 + carry;
            carry = sum / 10;
            int remainder = sum % 10;
            cur.next = new ListNode(remainder);
            cur = cur.next;
            if (p1 != null) {
                p1 = p1.next;
            }
            if (p2 != null) {
                p2 = p2.next;
            }
        }
        return reverseList(dummy.next);
    }
    private ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
}

BM12. 单链表的排序

方法一：归并排序（推荐使用）
具体做法：
前面我们做合并两个有序链表不是使用归并思想吗？说明在链表中归并排序也不是不可能使用，合并阶段可以参照前面这道题，两个链表逐渐取最小的元素就可以了，但是划分阶段呢？
常规数组的归并排序，是将数组从中间个元素开始划分，然后将划分后的子数组作为一个要排序的数组，再将排好序的两个子数组合并成一个完整的有序数组，因此采用的是递归。而链表中我们也可以用同样的方式，只需要找到中间个元素的前一个节点，将其断开，就可以将链表分成两个子链表，然后继续划分，直到最小，然后往上依次合并。

• step 1：首先判断链表为空或者只有一个元素，直接就是有序的。
• step 2：准备三个指针，快指针right每次走两步，慢指针mid每次走一步，前序指针left每次跟在mid前一个位置。三个指针遍历链表，当快指针到达链表尾部的时候，慢指针mid刚好走了链表的一半，正好是中间位置。

• step 3：从left位置将链表断开，刚好分成两个子问题开始递归。

  • 终止条件： 当子链表划分到为空或者只剩一个节点时，不再继续划分，往上合并。
  • 返回值： 每次返回两个排好序且合并好的子链表。
  • 本级任务： 找到这个链表的中间节点，从前面断开，分为左右两个子链表，进入子问题排序。

• step 4：将子问题得到的链表合并，参考合并两个有序链表。

  public class Solution {
    public ListNode sortInList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode left = head;
        ListNode mid = head.next;
        ListNode right = head.next.next;
        // 1. mid 走到链表中间，right走到null
        while (right != null && right.next != null) {
            left = left.next;
            mid = mid.next;
            right = right.next.next;
        }
        // 2. 断开链表
        left.next = null;
        // 3. 合并左右两个子链表
        return merge(sortInList(head), sortInList(mid));
    }
    private ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 != null) {
            cur.next = head1;
        } else {
            cur.next = head2;
        }
        return dummyHead.next;
    }
  }

方法二：转化为数组排序（扩展思路）
具体做法：
链表最难受的就是不能按照下标访问，只能逐个遍历，那像排序中常规的快速排序、堆排序都不能用了，只能用依次遍历的冒泡排序、选择排序这些。但是这些复杂度的排序方法太费时间了，我们可以将其转化成数组后再排序。

• step 1：遍历链表，将节点值加入数组。
• step 2：Java或者C++内置的排序函数对数组进行排序。
• step 3：依次遍历数组和链表，按照位置将链表中的节点值修改为排序后的数组值。 ```java import java.util.*;

// 方法2：转换成数组排序 public class Solution { public ListNode sortInList(ListNode head) { if (head == null) { return head; }

    List<Integer> list = new ArrayList<>();
    ListNode cur = head;
    while (cur != null) {
        list.add(cur.val);
        cur = cur.next;
    }
    Collections.sort(list);
    cur = head;
    for (int i = 0; i < list.size(); i++) {
        cur.val = list.get(i);
        cur = cur.next;
    }
    return head;
}

}

<a name="OSH2P"></a>
#### BM13. [判断一个链表是否为回文结构](https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f?tpId=295&sfm=html&channel=nowcoder)
**方法1：栈**<br />逆序访问，我们可以借助先进先出的栈：根据链表顺序入栈的元素，越在前面的就越在栈底，越在后面的就越在栈顶，因此后续从栈中弹出的元素，依次就是链表的逆序。也可以用ArrayList 随机访问数组这些类似的结构。
- step 1：遍历链表，将链表元素依次加入栈中。
- step 2：依次从栈中弹出元素值，和链表的顺序遍历比较，如果都是一一比较相同的值，那正好就是回文，否则就不是。
```java
import java.util.*;
public class Solution {
    // 方法1：栈
    public boolean isPail(ListNode head) {
        ListNode cur = head;
        Deque<Integer> stack = new ArrayDeque<>();
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        cur = head;
        while (!stack.isEmpty()) {
            // 比较是否相同
            if (cur.val != stack.pop()) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }
}

方法2：双指针中点反转法

• step 1：慢指针每次走一个节点，快指针每次走两个节点，快指针到达链表尾的时候，慢指针刚好到了链表中点，链表结点个数为奇数时，慢指针刚好到中间的那个结点；个数为偶数时，慢指针会到右半段的开头位置。
• step 2：从中点的位置，开始往后将后半段链表反转。
• step 3：按照方法四的思路，左右双指针，左指针从链表头往后遍历，右指针从链表尾往反转后的前遍历，依次比较遇到的值。

public class Solution {
    // 方法2：双指针反转链表法
    public boolean isPail(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverse(slow);
        fast = head;
        while (slow != null) {
            if (slow.val != fast.val) {
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode pNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = pNext;
        }
        return pre;
    }
}

BM14. 链表的奇偶重排

方法1：双指针。

• step 1：判断空链表的情况，如果链表为空，不用重排。
• step 2：使用双指针odd和even分别遍历奇数节点和偶数节点，并给偶数节点链表一个头。
• step 3：上述过程，每次遍历两个节点，且even在后面，因此每轮循环用even检查后两个元素是否为NULL，如果不为再进入循环进行上述连接过程。
• step 4：将偶数节点头接在奇数最后一个节点后，再返回头部。

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        // 1. 双指针，分别指向奇偶位置
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = head.next;
        // 2. 依次修改链接，并移动指针
        while (even != null && even.next != null) {
            // odd 连接偶数的下一个，再移动
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        // 3. 偶数整体连接在奇数后面
        odd.next = evenHead;
        return head;
    }
}

BM15. 删除有序链表中重复的元素-I

方法：遍历删除（推荐使用）
具体做法：
既然相同的元素只留下一个，我们留下哪一个最好呢？当然是遇到的第一个元素了！因为第一个元素直接就与前面的链表节点连接好了，前面就不用管了，只需要跳过后面重复的元素，连接第一个不重复的元素就可以了，在链表中连接后面的元素总比连接前面的元素更方便嘛，因为不能逆序访问。

• step 1：判断链表是否为空链表，空链表不处理直接返回。
• step 2：使用一个指针遍历链表，如果指针当前节点与下一个节点的值相同，我们就跳过下一个节点，当前节点直接连接下个节点的后一位。
• step 3：如果当前节点与下一个节点值不同，移动指针，继续往后遍历。
• step 4：循环过程中每次用到了两个节点值，要检查连续两个节点是否为空。

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

BM16. 删除有序链表中重复的元素-II

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

方法一：直接比较删除（推荐使用）
具体做法：
这是一个升序链表，重复的节点都连在一起，我们就可以很轻易地比较到重复的节点，然后去删除。

• step 1：给链表前加上表头，方便可能的话删除第一个节点。
• step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻结点相同，则新开内循环将这一段所有的相同都遍历过去。
• step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
• step 4：返回时去掉添加的表头。

// 1. 直接比较删除
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int aimVal = cur.next.val;
                while (cur.next != null && cur.next.val == aimVal) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

方法二：哈希表（扩展思路）
具体做法：
这道题幸运的是链表有序，我们可以直接与旁边的元素比较，然后删除重复。那我们扩展一点，万一遇到的链表无序呢？我们这里给出一种通用的解法，有序无序都可以使用，即使用哈希表来统计是否重复。

• step 1：遍历一次链表用哈希表记录每个结点值出现的次数。
• step 2：在链表前加一个结点值为0的表头，方便可能的话删除表头元素。
• step 3：再次遍历该链表，对于每个结点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。
• step 4：返回时去掉增加的表头。

import java.util.*;
public class Solution {
    // 方法2：哈希表
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        // 1. 创建哈希表
        Map<Integer, Integer> map = new HashMap<>();
        ListNode cur = head;
        // 2. 遍历链表，在哈希表中存储结点的值、和该值出现的次数
        while (cur != null) {
            if (map.containsKey(cur.val)) {
                int count = map.get(cur.val);
                map.put(cur.val, count + 1);
            } else {
                map.put(cur.val, 1);
            }
            cur = cur.next;
        }
        // 3. 再次遍历链表，只留下次数为1
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        cur = dummyHead;
        while (cur.next != null) {
            if (map.get(cur.next.val) != 1) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummyHead.next;
    }
}

专题2：二分查找和排序

BM17. 二分查找-I

既然数组是升序且无重复的，可以使用二分法。

• step 1：从数组首尾开始，每次取中点值。
• step 2：如果中间值等于目标即找到了，可返回下标，如果中点值大于目标，说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。
• step 3：根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。

二分查找，求解mid 的时候，可以用(right - left) / 2，或者是>> 1 右移运算符。

import java.util.*;
public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

BM18. 二维数组中的查找

方法1：二分法。
既然矩阵里面的元素是有序且无重复的，我们可以好好利用一下。首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。我们可以在查找时使用二分法

• step 1：首先获取矩阵的两个边长，判断特殊情况。
• step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。

• step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。

  public class Solution {
    public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0) {
            return false;
        }
        int row = array.length - 1;
        int col = 0;
        while (row >= 0 && col < array[0].length) {
            if (array[row][col] < target) {
                col++;
            } else if (array[row][col] > target) {
                row--;
            } else {
                return true;
            }
        }
        return false;
    }
  }

BM19. 寻找峰值

方法1：二分查找
具体做法：
因为数组边界看成最小值，因此只要不断地往高处走，一定会有波峰，最大值两边一定比它小。那可以考虑二分查找。

• step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
• step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
• step 3：如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
• step 4：最后区间收尾相遇的点一定就是波峰。

数组边界看成最小值，因此只要不断地往高处走，一定会有波峰.

public class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                // 往上走，一定能找到波峰
                left = mid + 1;
            }
        }
        return right;
    }
}

BM20. 数组中的逆序对

方法一：归并排序(推荐使用)
具体做法：
因为我们在归并排序过程中会将数组划分成最小为2个元素的子数组，然后依次比较子数组的长度，这里我们也可以用相同的方法统计逆序对。我们主要有三个阶段：

• step 1： 划分阶段：将待划分区间从中点划分成两部分；
• step 2： 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对；
• step 3： 合并阶段：将排好序的子序列合并，同时累加逆序对。

因为在归并排序中，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。

归并排序的典型应用。实际上是一个分治问题，不断将数组一分为二，直到数组中只有两个元素，然后对这一对进行merge，此时就是统计逆序对的最佳时机。

// 方法1：归并排序
public class Solution {
    public int InversePairs(int[] array) {
        if (array.length < 2) {
            return 0;
        }
        int count = divide(array, 0, array.length - 1);
        return count % 1000000007;
    }
    // 1. 分治
    public int divide(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        // 得到左右两半边、和合并以后的逆序对个数
        int leftCount = divide(arr, left, mid);
        int rightCount = divide(arr, mid + 1, right);
        int mergeCount = merge(arr, left, mid, right);
        return leftCount + rightCount + mergeCount;
    }
    // 2. 合并
    public static int merge(int[] arr, int left, int mid, int right) {
        if (left > right) {
            return 0;
        }
        // 1. 辅助数组，依次比较两个有序数组，把元素按顺序填进去
        int[] help = new int[right - left + 1];
        int count = 0;
        // 2. 三个指针，分别指向三个数组
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        // 3. 对两个有序数组进行合并，并统计逆序对
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                help[index++] = arr[p1++];
            } else {
                help[index++] = arr[p2++];
                // 计算左边数组有几个大于右边的
                count += mid - p1 + 1;
            }
        }
        // 4. 添加剩余的部分
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= right) {
            help[index++] = arr[p2++];
        }
        // 5. 把排好序的数组覆盖到原数组
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
        // 6. 返回
        return count % 1000000007;
    }
}

BM21. 旋转数组的最小数字

题目的主要信息：
有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组
找到这个旋转数组的最小值

方法一：二分法（推荐使用）
具体做法：
因为旋转数组将原本有序的数组分成了两部分有序的数组，因为在原始有序数组中，最小的元素一定是在首位，旋转后无序的点就是最小的数字。我们可以将旋转前的前半段命名为A，旋转后的前半段命名为B，旋转数组即将AB变成了BA。
可以依旧利用二分的思想，分情况讨论：

• step 1：双指针指向旋转后数组的首尾，作为区间端点。
• step 2：若是区间中点值大于区间右界值，则最小的数字一定在中点右边。
• step 3：若是区间中点值等于区间右界值，则是不容易分辨最小数字在哪半个区间，比如[1,1,1,0,1]，应该逐个缩减右界；
• step 4：若是区间中点值小于区间右界值，则最小的数字一定在中点左边。
• step 5：通过调整区间最后即可锁定最小值所在。

解题思路：排序数组首先考虑二分法。旋转数组将原本有序数组的前面部分截取，挪到了后面，即前面部分的元素都大于等于后面最大的。设置三个指针，left、mid、right，当arr[mid] > arr[right]，说明mid 位置的元素本身就在这儿，没有截取挪动过，此时就可以缩小排查范围，旋转点在[mid+1, right] 区间内。

public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < array[right]) {
                right = mid;
            } else if (array[mid] > array[right]) {
                // 说明最小数字肯定在mid 的右边
                left = mid + 1;
            } else {
                // 无法判断，right 范围缩小1
                right--;
            }
        }
        return array[left];
    }
}