1. 链表
- 反转链表：用头插法就可以。
- 反转局部链表：如图所示，反转2 3 4 的操作。
![[牛客101题 2023-09-27 23.32.49.excalidraw]]
- 链表中每k个一组反转：调用反转局部链表
- 合并两个有序链表：按大小顺序将节点添加到一个新的节点上。
- 合并k个有序链表：
- 调用合并两个有序链表：超时
- 二分法后调用合并两个有序链表
- 判断链表是否有环：快慢指针，当慢指针和快指针想等的时候，说明有环
- 链表中环的起始节点：
- 获取环的长度length，然后从首节点遍历，节点n和节点n+length想等的话n节点是环的起始节点
- 数学关系：
- ![[牛客101题 2023-09-28 00.00.40.excalidraw]]
2. 二分排序/查找
- 数组中的逆序对：
- 暴力：时间空间都差
- 二分归并：
public class Solution { public int mod = 1000000007; public int mergeSort(int left, int right, int [] data, int [] temp){ //停止划分 if(left >= right) return 0; //取中间 int mid = (left + right) / 2; //左右划分合并 int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //防止溢出 res %= mod; int i = left, j = mid + 1; for(int k = left; k <= right; k++) temp[k] = data[k]; for(int k = left; k <= right; k++){ // 左边遍历完毕，把右边的全部放在总数组 if(i == mid + 1) data[k] = temp[j++]; // 右边数组遍历完毕或者 左边数组元素比右边小，那么就直接按顺序放在总数组 else if(j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; //左边比右边大，那么这个元素temp[i]到mid-1之间的元素都比右边数组这个元素大，逆序对个数就增加增加mid-1+i个 else{ data[k] = temp[j++]; // 统计逆序对 res += mid - i + 1; } } return res % mod; } public int InversePairs(int [] array) { int n = array.length; int[] res = new int[n]; return mergeSort(0, n - 1, array, res); } }
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。也可以邮件至 2738430398@qq.com