牛客刷题题解暂记

地址：算法篇题目
记录一下刷题时的问题，待晚上整理题解报告

• BM1 反转链表：核心思想就是将插入的位置改一下，从链表头部插入就成了逆序
• BM2 指定反转：核心思想是标记一个反转区间的前驱指针（插入位置），后续插入的将从这里插入
• BM3 每k组反转：核心思想是利用一个慢指针指向第i组的第一个元素，然后扫描到最后一个元素，再利用尾指针进行逆序插入（需要维护好尾指针），最后将剩余不足一组的元素进行顺序插入到尾部。
• BM4 简单的合并，比较大小合并。然后将剩余的直接加入链表尾部即可。
• BM5 暴力挨个合并（或者拆分数组，每次折半合并），也可以考虑全部取出来进行排序
• BM6 利用两倍步进（走二进一）的快慢指针，当快指针追上慢指针时说明有环，否则快指针必然会走到null的链表尾部
• BM7 利用BM5的结论，推理得到当他们相遇时一定是两倍关系（前提是快指针必须是走满两步后碰到的慢指针，比如快指针走了第一步就遇见了慢指针这种情况不算），因此能够得出l + x = nH的结论（l为不为环的长度包括入环的点，H表示环的长度，x表示入环位置到第一次快慢指针相遇的距离）
• BM8 利用快慢指针，当快指针步进达到k时，慢指针开始同步移动直到快指针走完。
• BM9 利用快慢指针，当快指针步进达到 n + 1时，慢指针开始同步移动，最终指向倒数第 n + 1个元素（定义一个前驱指针指向head），然后删除第n个元素即可，需要处理删的是head的情况。
• BM10 利用l1 + l2长度一致， 让指针遍历两条链，相交的点就是第一个公共节点（nil就说明跑到头了都没碰到），因为相同速度，相同距离，肯定会相遇的（将两条链拼起来对比就看出来了）
• BM11 大模拟，反转两条链表，然后带进位的进行大数加法的模拟，最后把结果链反转一下
• BM12 链表上进行快排超时了，使用归并排序没问题。（还有一种方式就是利用数组辅助进行快排）
• BM13 反转链表之后判断一遍即可
• BM14 利用两个指针，一个指向奇数位的尾部，一个指向偶数位的尾部。每次插值往这两个中的一个插入即可，偶数位再第一次要赋值未奇数位（因为奇数位肯定是第一个节点）
• BM15 挨个判断下一个是否相等即可，相等就删除。注意空链表的情况
• BM16 找到下一个不相等的元素，如果距离大于1，就删除这个区间的所有节点。所以需要一个删除的起始点指针，当没有相等元素时就跟随指针移动。