【记录】算法 - C/C++版

基础 输入输出

【输入输出格式 - 算法笔记P19】

输入输出使用scanf和printf。（因为scanf和printf的运行速度比cin和cout快）

异或

• 相异为1，相同为0。
• N^0=N，NN=0。
• 满足交换律和结合律。

// 数组中有一个数只出现奇数次，其余都出现偶数次。请找出这个数。 
// leetcode-136 
// 时间复杂度O(n)，空间复杂度O(1)
int findNum(vector& nums){
	int res = 0;
	for(int n : nums){
		res ^= n;
	}
	return res;
}
// 数组中有两个数只出现奇数次，其余都出现偶数次。请找出这两个数。 
// leetcode-260 
// 时间复杂度O(n)，空间复杂度O(1)
vector findNums(vector& nums){
	int eor = 0;
	for(int n : nums){
		eor ^= n;
	}
	// eor=a^b，且不等于0。
	// eor&（eor的补码）找出eor二进制表示中为1的最低位。
	// 判断eor是不是INT_MIN，如果等于INT_MIN，取反会溢出。
	int right = eor == INT_MIN ? eor : eor & (-eor);
	int one = 0; // 得到a或b。
	for(int n : nums){
		// 根据right位的不同分类异或。
		if(n & right){
			one ^= n;
		}
	}
	vector res;
	res.push_back(one);
	res.push_back(one^eor);
	return res;
}

交换

void swap(vector& nums, int i, int j){
	// 临时变量
	int temp = nums[i];
	num[i] = nums[j];
	nums[j] = temp;
	
	// 加减（定义了加减法的数据结构才能用）
	nums[i] = nums[i] + nums[j];
	nums[j] = nums[i] - nums[j];
	nums[i] = nums[i] - nums[j];
	
	// 异或（地址值i和j必须不同，但地址所存储的值可以一样（会将该地址所存储的值抹为0，相当于自己地址值里的内容跟自己地址值里的内容异或=0））
	nums[i] = nums[i] ^ nums[j];
	nums[j] = nums[i] ^ nums[j];
	nums[i] = nums[i] ^ nums[j];
}

递归

master公式

• T(N) = a*T(N/b) + O(N^d)
• 适用于子问题等规模的递归，求解母问题的时间复杂度。
• （1）log(b, a) > d => 复杂度为O( N^log(b, a) )
• （2）log(b, a) = d => 复杂度为O( N^d * logN)
• （3）log(b, a) < d => 复杂度为O( N^d )

随机数

#include 
#include 
...
int main(){
	// 生成随机种子
	srand((unsigned)time(NULL));
	// 生成随机数[0, RAND_MAX]
	cout << rand() << endl;
	// [0, 1]
	cout << rand() % 2 << endl;
	cout << rand() / RAND_MAX << endl;
	// [x, y]
	cout << rand() % (y-x) + x << endl;
	cout << (int)round(1.0 * rand() / RAND_MAX * (y - x) + x) << endl;
}

排序

基于比较的排序

选择排序

• 当前指向i位置，每次从i之后的序列中选出最小值，交换i和最小值。
• 时间复杂度O（n^2）
• 空间复杂度O（1）
• 不稳定

void selection(vector& nums){
	if(nums.size() < 2) return;
	// 长度n，下标0～n-1
	// 遍历i～n-2
	for(int i = 0; i < nums.size()-1; i++){
		int min = i;
		// 遍历i+1～n-1
		for(int j = i + 1; j < nums.size(); j++){
			min = nums[j] < nums[min] ? j : min;
		}
		swap(nums, i, min);
	}
}

冒泡排序

• 从前往后，两两比较，大的往后放，每次比较后冒出一个最大的元素。
• 时间复杂度O（n^2）
• 空间复杂度O（1）
• 稳定

void bubbleSort(vector& nums){
	if(nums.size() < 2) return;
	// i放每趟排序后冒出来的元素
	for(int i = nums.size()-1; i > 0; i--){
		// 遍历0～i-1
		for(int j = 0; j < i; j++){
			if(nums[j] > nums[j+1]) swap(nums, j, j+1);
		}
	}
}

插入排序

• 将元素从后往前插入已排序序列中，比较直到前一个元素比元素小结束。
• 时间复杂度O（n^2）
• 空间复杂度O（1）
• 稳定

void insertSort(vector& nums){
	if(nums.size() < 2) return;
	// i指向待插入元素。
	for(int i = 1; i < nums.size(); i++){
		// j指向i前面元素，比较j和j+1。
		for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--){
			swap(nums, j, j+1);	
		}
	}
}

归并排序

• 分成左右两序列，使左右序列分别有序；合并左右序列，小的插入result，指针后移。
• 时间复杂度O(NlogN)
• 空间复杂度O(N)
• 稳定

void merge(vector& arr, int L, int mid, int R){
	vector result(R-L+1);
	// 数组版本
	// int result[R-L+1];
	int i = 0;// 指向result数组当前要放入元素的位置
	int p1 = L;// 指向左序列当前遍历到哪里
	int p2 = mid + 1;// 指向右序列当前遍历到哪里
	while(p1 <= M && p2 <= R){
		// 注意是<=（相等时优先把左序列插入）
		result[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
	}
	// 遍历结束还有元素未插入
	while(p1 <= M){
		result[i++] = arr[p1++];
	}
	while(p2 <= R){
		result[i++] = arr[p2++];
	}
	for(int j = 0; j < i; j++){
		arr[L+j] = result[j];
	}
}
void process(vector& arr, int L, int R){
	if(L == R) return;
	//mid = L + (R-L)/2；为了防止溢出，mid = L + (R-L)/2；位运算更快。
	int mid = L + ((R - L) >> 1);
	process(arr, L, mid);
	process(arr, mid+1, R);
	merge(arr, L, mid, R);
}
void mergeSort(vector& nums){
	if(nums.size() < 2) return;
	process(nums, 0, nums.size()-1);
}


// 应用 
// 小和问题：在一个数组中，遍历每个数，把每个数左边比当前数小的数累加起来，叫做这个数组的小和。
int merge(vector& arr, int L, int mid, int R){
	vector result(R-L+1);
	int i = 0;
	int p1 = L;
	int p2 = mid+1;
	int res = 0;
	while(p1 <= mid && p2 <= R){
		res += arr[p1] < arr[p2] ? (R-p2+1) * arr[p1] : 0;
		// 注意是<（优先让右序列插入，保证p2指向正确、小和正确）
		result[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
	}
	while(p1 <= mid){
		result[i++] = arr[p1++];
	}
	while(p2 <= R){
		result[i++] = arr[p2++];
	}
	for(int j = 0; j < i; j++){
		arr[L+j] = result[j];
	}
	return res;
}
int process(vector& arr, int L, int R{
	if(L == R) return 0;
	int mid = L + ((R-L)>>1);
	return process(nums, L, mid)
		+ process(nums, mid+1, R)
		+ merge(nums, L, mid, R);
}
int smallSum(vector& nums){
	if(nums.size() < 2) return 0;
	return process(nums, 0, nums.size()-1);
}
// 逆序对问题：在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请求出逆序对的总数。 
// leetcode-剑指offer51
int merge(vector& nums, int l, int mid, int r){
	vector result(r-l+1);
	int i = 0;
	int p1 = l;
	int p2 = mid+1;
	int res = 0;
	while(p1 <= mid && p2 <= r){
		res += nums[p1] > nums[p2] ? r-p2+1 : 0;
		result[i++] = nums[p1] > nums[p2] ? nums[p1++] : nums[p2++];
	}
	while(p1 <= mid){
		result[i++] = nums[p1++];
	}
	while(p2 <= r){
		result[i++] = nums[p2++];
	}
	for(p1 = 0; p1 < i; p1++){
		nums[l+p1] = result[p1];
	}
	return res;
}
int process(vector& nums, int l, int r) {
	if(l == r) return 0;
	int mid = l + ((r-l)>>1);
	return process(nums, l, mid)
		+ process(nums, mid+1, r)
		+ merge(nums, l, mid, r);
}
int reversePairs(vector& nums) {
	if(nums.size() < 2) return 0;
	return process(nums, 0, nums.size()-1);
}

快速排序

• 时间复杂度O(NlogN)
• 空间复杂度O(logN)
• 不稳定

// 问题1：给定一个数组arr和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。 
vector divide(vector& arr, int num){
	int i = -1;// 指向<=区的最后一个元素
	int p = 0;
	while(p < arr.size()){
		// <=num, 和i的下一个数交换（插入<=区，<=区右扩）
		if(arr[p] <= num){
			swap(arr, ++i, p);
		}
		// >num，不做处理

		p++;
	}
	return arr;
}

// 荷兰国旗问题：给定一个数组arr和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
vector dutchNationalFlag(vector arr, int num){
	int l = -1;
	int b = arr.size();
	int p = 0;
	while(p < arr.size()){
		// 
			swap(arr, p++, ++l);
		}
		// =num，p右移。
		else if(arr[p] == num){
			p++;
		}
		// >num，和j的前一个数交换（>区左扩），p不动（交换后p还未被比较过）
		else{
			swap(arr, p, b);
		}
	}
	return arr;
}

//快排1.0：最后一个数为num，以问题1为partition算法，不断递归。
//快排2.0：最后一个数为num，以荷兰国旗问题为partition算法，不断递归。
//快排3.0：随机一个数为num，以荷兰国旗问题为partition算法，不断递归。
vector partition(vector& nums, int l, int r){
	int i = l - 1;
	int j = r;// r位置是标杆
	int p = l;
	while(p < j){
		if(nums[p] < nums[r]){
			swap(nums, p++, ++i);
		}else if(nums[p] == nums[r]){
			p++;
		}else{
			swap(nums, p, --j);
		}
	}
	// >区的左边界和标杆换位置
	swap(nums, j, r);
	// 返回=区的左右边界
	vector res {i+1, j};
	return res;
	
}
vector process(vector& nums, int l, int r){
	if(l < r){
		// 挑一个随机数和r交换做标杆
		swap(nums, round(1.0*rand()/RAND_MAX*(r-l)+l, r);
		// p[0]是=区的左边界，p[1]是=区的右边界
		vector p = partition(nums, l, r);
		// <区再做快排
		process(nums, l, p[0]-1);
		// >区再做快排
		process(nums, p[1]+1, r);
	}
	return nums;
}
vector quickSort(vector& nums){
	if(nums.size() < 2) return nums;
	return process(nums, 0, nums.size()-1);
}

// 优化：样本数<60使用插入排序；其余使用快排。

堆排序

• 时间复杂度O(NlogN)
• 空间复杂度O(1)
• 不稳定
• 优先队列结构就是堆结构。

// 完全二叉树中，（结点下标为i），i结点的父结点为(i-1)/2，左孩子2i+1，右孩子2i+2。

// 给了个大根堆，从index位置开始往上调整成大根堆。 
// 不断跟父节点比较，比父节点大上浮。 
// 时间复杂度O(logN)
void heapInsert(vector& arr, int index){
	// 比父亲小 或 我的父亲就是我自己 时跳出循环。
	while(arr[index] > arr[(index-1)/2]){
		swap(arr, index, (index-1)/2);
		index = (index - 1)/2;
	}

}

// 给了个大根堆，从index位置开始往下调整成大根堆。 
// 不断跟子节点较大的比较，比子节点小下沉。 
// 时间复杂度O(logN)
void heapify(vector& arr, int index, int heapSize){
	int lchild = index*2+1;
	while(lchild < heapSize){
		// 左右孩子进行比较
		int bigOne = lchild+1 < heapSize && arr[lchild] < arr[lchild+1] ? lchild+1 : lchild;
		// 左右孩子中较大的和父亲进行比较
		bigOne = arr[bigOne] > arr[index] ? bigOne : index;
		if(bigOne == index) break;
	
		swap(arr, bigOne, index);
		index = bigOne;
		lchild = index * 2 + 1;
	}
}

// 给了个大根堆，把index位置改成某个数num，要求调整成大根堆。 
// num和arr[index]进行比较，如果numarr[index]往上调整。

// 堆排序
void heapSort(vector& arr){
	if(arr.size() < 2) return;
	// 从0位置开始插入, 建立大根堆
	// for(int i = 0; i < arr.size(); i++){
		// heapInsert(arr, i);
	// }

	int heapSize = arr.size();
	// 倒序遍历，向下调整大根堆
	for(int i = arr.size()-1; i >= 0; i--){
		heapify(arr, i, heapSize);
	}

	// 不断把最大的摘下来，放在最后
	swap(arr, 0, --heapSize);
	while(heapSize > 0){
		heapify(arr, 0, heapSize);
		swap(arr, 0, --heapSize);
	}
}

// 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
void sortedArrDistanceLessK(vector& arr, int k){
	priority_queue heap;
	int index = 0;// 指向数组遍历到哪
	// 把数组前k个数放入堆内，调整堆。
	// 求出数组长度和k中的最小值（防止k>>数组长度）
	for(; index < min(arr.size() , k); index++){
		heap.push(arr[index]);
	}
	int i = 0;// 指向结果放到哪
	// 不断把第k+1个数放进堆里，调整堆，弹出堆顶
	for(; index < arr.size(); i++, index++){
		heap.push(arr[index]);
		// 弹出堆顶，放在i位置上
		arr[i] = heap.pop();
	}
	while(!heap.empty()){
		arr[i++] = heap.pop();
	}	
}

非基于比较的排序

• 根据数据对象决定排序方法。

计数排序

• 建立数组，下标即为数字，统计数字出现的频率。

桶排序（基数排序）

• 不稳定

#include 
const radix = 10;
int getDigit(int x, int d){
	return ((x / pow(10, d-1))%10);
}
void radixSort(vector& arr, int l, int r, int digit){
	int i = j = 0;
	vector bucket(r-l+1);
	for(int d = 1; d <= digit; d++){
		// 原count数组，count[i]表示d位上，i出现的次数。 
		// 现count数组，count[i]等于count[i]前面的数字累加，表示d位上<=i的有几个（每个数字的片加起来）；每个数该放在bucket数组下标=count[i]-1。
		vector count(radix);
		// 统计出现的次数
		for(i = l; i <= r; i++){
			j = getDigit(arr[i], d);
			count[j]++;
		}
		// 累加
		for(i = 1; i < radix; i++){
			count[i] += count[i-1];
		}
		// 从右往左遍历数组（保证先入先出）
		for(i = r; i >= l; i--){
			j = getDigit(arr[i], d);
			bucket[count[j]-1] = arr[i];
			count[j]--;
		}
		for(i = l, j = 0; i <= r; i++, j++){
			arr[i] = bucket[j];
		}
	}
}
// 求最多有几位radix
int maxbits(vector& arr){
	int max = INT_MAX;
	for(int i = 0; i < arr.size(); i ++){
		max = max(max, arr[i]);
	}
	int res = 0;
	while(max != 0){
		res++;
		max /= radix;
	}
	return res;
}
vector radixSortMain(vector& arr){
	if(arr == null || arr.size() < 2) return arr;
	radixSort(arr, 0, arr.size()-1, maxbits(arr));
	return arr;
}

数组 二分查找

找某个数

• 有序数组，找某个数是否存在。
• 时间复杂度O（logN）

// 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
// leetcode-704
// 1、左闭右闭[left, right]
int search(vector& nums, int target) {
	int left = 0;
	int right = nums.size()-1;
	int middle;
	// 问题1：是<=还是<？
	// 答：因为这里是左闭右闭，举特殊例子，当区间[1, 1]时，left=right是有意义的，仍要进行查找，所以是<=。
	while(left <= right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] > target){
			// 更新右边界
			// 问题2：是middle还是middle-1？
			// 答：middle已经判断过了，所以是middle-1
			right = middle - 1;
		}else if(nums[middle] < target){
			// 更新左边界
			left = middle + 1;
		}else{
			return middle;	
		}
	}
	return -1;
}
// 2、左闭右开[left, right)
int search(vector& nums, int target) {
	int left = 0;
	// 左闭右开，右边界不包含
	int right = nums.size();
	int middle;
	// 当left=right，[1, 1)不合法，所以是<
	while(left < right){
		middle = l + (r - l) >> 1;
		if(nums[middle] > target){
			// 更新右边界，右开，将右边界定为middle
			right = middle;
		}else if(nums[middle] < target){
			// 更新左边界，左闭，将左边界定为middle+1（middle已经判断过）
			left = middle + 1;
		}else{
			return middle;
		}
	}
	return -1;
}

找最左侧

• 有序数组，找>=或者>某个数最左侧的位置。
• 时间复杂度O（logN）

// 找lower_bound：找>=某个数的第一个位置
// 左闭右开
int lower_bound(vector& nums, int target) {
	int left = 0;
	int right = nums.size();
	int middle;
	// left=right夹出唯一位置
	while(left < right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] >= target){
			// 更新右边界：middle左边可能还有>=target的
			right = middle;
		}else{
			// 更新左边界：>=target在middle右边
			left = middle + 1;
		}
	}		
	// 返回夹出来的位置
	return left;
}


// 找upper_bound：找>某个数的第一个位置
// 左闭右开
int upper_bound(vector& nums, int target){
	int left = 0;
	int right = nums.size();
	int middle;
	while(left < right){
		middle = left + ((right - left) >> 1);
		if(nums[middle] > target){
			// 更新右边界：middle左边可能还有>target的
			right = middle;
		}else{
			// 更新左边界：>target在middle右边
			left = middle + 1;
		}
	}
	return left;
}


// leetcode-35（可能不存在）
// 1、暴力解
int searchInsert(vector& nums, int target) {
	for(int i = 0; i < nums.size(); i ++){
		// 一旦发现>=目标值的就返回
		if(nums[i] >= target){
			return i;
		}
	}
	// 否则返回数组长度
	return nums.size();
}
// 2、二分查找（左闭右开）
int searchInsert(vector& nums, int target){
	int l = 0;
	int r = nums.size();
	int m;
	while(l < r){
		m = l + ((r-l) >> 1);
		if(nums[m] >= target){
			r = m;
		}else{
			l = m + 1;
		}
	}
	// 判断target是否存在于数组中
	
	// 判断l是否比所有数大
	if(l == nums.size()) return nums.size();
	return l;
}


// 找元素的第一个和最后一个位置
// leetcode-34
vector searchRange(vector& nums, int target) {
	if(nums.empty()) return {-1, -1};
	vector res;
	// 左闭右开
	int l = 0;
	int r = nums.size();
	int m;
	// 找<=target的右边界
	while(l < r){
		m = l + ((r-l)>>1);
		if(nums[m] >= target){
			r = m;
		}else{
			l = m + 1;
		}
	}
	// 查找失败先返回
	if(l == nums.size()) return {-1, -1};
	res.push_back(l);
	// 找>=target的右边界
	// 从上一步的r开始找
	l = r;
	r = nums.size();
	while(l < r){
		m = l + ((r-l) >> 1);
		if(nums[m] <= target){
			l = m + 1;
		}else{
			r = m;
		}
	}
	if(l-1 == nums.size()) return {-1, -1};
	res.push_back(l-1);
	if(res[1]>=res[0]){
		return res;
	}else{
		return {-1, -1};
	}
}

局部最小值
无序数组，相邻数一定不相等，求局部最小值。

• 时间复杂度O（n）

二分法的应用

// 算平方根
// leetcode-69
int mySqrt(int x) {
	// 题意相当于找m^2最接近x的最大的数
	// 特殊情况（0、1）返回
	if(x <= 1) return x;
	// 左闭右闭
	int l = 1, r = x / 2 + 1, m;// 当x>1且为整数时，根号x在[1,x/2+1]区间内
	while(l <= r){
		m = l + ((r-l) >> 1);
		if((long long)m*m < x){
			l = m + 1;// 更新右边界
		}else if((long long)m*m > x){
			r = m - 1;// 更新左边界
		}else{
			return m;
		}
	}
	// 如果不是通过m^2=x返回，则返回r
	return r;
}

// 判断是否为完美平方根
// leetcode-367
bool isPerfectSquare(int num) {
	int l = 1, r = num / 2 + 1, m;
	while(l <= r){
		m = l + ((r - l) >> 1);
		if((long long)m*m < num){
			l = m + 1;
		}else if((long long)m*m > num){
			r = m - 1;
		}else{
			return true;
		}
	}
	return false;
}

双指针

// leetcode-26

// leetcode-283

// leetcode-844
bool backspaceCompare(string s, string t) {
	int i = -1;// s有效序列
	for(int k = 0; k < s.length(); k++){
		if(s[k] == '#'){
			if(i>-1){//有路可退，退退退！
				i--;
			}
		}else{
			s[++i] = s[k];//让k指向的元素纳入有效序列
		}
	}
	int j = -1;// t有效序列
	for(int p = 0; p < t.length(); p++){
		if(t[p] == '#'){
			if(j > -1){
				j--;
			}
		}else{
			t[++j] = t[p];
		}
	}
	if(i == -1||j == -1){//最后剩余的是空格
		return i == j;
	}
	// substr(开始位置，截取长度)
	return s.substr(0, i+1) == t.substr(0,j+1);
}

// leetcode-977
// 方法1：双指针从中间开始移动（小的先插入）
vector sortedSquares(vector& nums) {
	vector res;
	int i = 0, j = 0; // i负数列，j正数列
	while(j
		j++;//1
	}
	i = j - 1;//0
	while(i >= 0 && j < nums.size()){
		if(abs(nums[i]) <= nums[j]){
			res.push_back(nums[i]*nums[i]);
			i--;
		}else{
			res.push_back(nums[j]*nums[j]);
			j++;
		}
	}
	while(i >= 0){
		res.push_back(nums[i]*nums[i]);
		i--;
	}
	while(j < nums.size()){
		res.push_back(nums[j]*nums[j]);
		j++;
	}
	return res;
}
// 方法2：双指针分别从两端开始移动（大的先插入）
vector sortedSquares(vector& nums) {
	vector res(nums.size());
	int k = res.size()-1;
	for(int i = 0, j = nums.size()-1; i <= j;){
		if(nums[i]*nums[i] >= nums[j]*nums[j]){
			res[k--] = nums[i]*nums[i];
			i++;
		}else{
			res[k--] = nums[j]*nums[j];
			j--;
		}
	}
	return res;
}

滑动窗口*

// leetcode-209
int minSubArrayLen(int target, vector& nums) {
	int result = INT32_MAX;// 记录最小长度
	int sum = 0;// 记录子序列和
	int i = 0;// 起始位置
	int subLength = 0;// 子序列长度
	// 终止位置
	for(int j = 0; j < nums.size(); j++){
		// 累加
		sum += nums[j];
		while(sum >= target){
			// 更新最小长度
			subLength = j - i + 1;
			result = result < subLength ? result : subLength;
			// 把滑动窗口头摘下来，更新i
			sum -= nums[i++];
		}
	}
	return result == INT32_MAX ? 0 : result;
}

// leetcode-904
int totalFruit(vector& fruits) {
	int result;// 记录最大长度
	unordered_map m;// type, count
	int i = 0;// 起始位置
	int len = 0;// 记录子序列最大长度
	// 终止位置
	for(int j = 0; j < fruits.size(); j++){
		// 累加
		m[fruits[j]] ++;
		len ++;
		while(m.size()>2){
			// 把头摘下来
			m[fruits[i]] --;
			if(m[fruits[i]] == 0){
				m.erase(fruits[i]);
			}
			i++;
			len--;
		}
		// 更新最大长度
		result = result < len ? len : result;
	}
	return result;
}
    
// leetcode-76

螺旋矩阵* 哈希表 链表 单链表定义

struct ListNode{
	int val;
	ListNode* next;
	// 构造函数
	ListNode(int x): val(x), next(null) {}
}

删除链表元素

// leetcode-203
// 1、分情况讨论
ListNode* removeElements(ListNode* head, int val) {
	// 删除头节点
	while(head != NULL && head->val == val){
		ListNode* tmp = head;
		head = head->next;
		delete tmp;
	}
	// 删除非头节点
	ListNode* curr = head;
	// 注意可能存在删到最后空了
	while(curr != NULL && curr->next != NULL){
		if(curr->next->val == val){
			// 删除curr->next
			ListNode* tmp = curr->next;
			curr->next = curr->next->next;
			delete tmp;
		}else{
			curr = curr->next;
		}
	}
	return head;
}
// 2、添加虚拟节点
ListNode* removeElements(ListNode* head, int val) {
	// 设置一个虚拟头节点
	ListNode* h = new ListNode(0);
	// next指向链表头
	h->next = head;
	ListNode* curr = h;
	while(curr->next != NULL){
		if(curr->next->val == val){
			ListNode* tmp = curr->next;
			curr->next = curr->next->next;
			delete tmp;
		}else{
			curr = curr->next;
		}
	}
	// 删除虚拟头节点
	head = h->next;
	delete h;
	return head;
}

反转链表

// 反转单链表
// leetcode-206
// 1、指针法
ListNode* reverseList(ListNode* head) {
	ListNode* prev = NULL;
	ListNode* curr = head;
	ListNode* next = head;
	while(curr != NULL){
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}
// 2、递归法
ListNode* reverseList(ListNode* head) {
	// 递归的边界
	if(head == NULL || head->next == NULL){
		return head;
	}
	// last用来指向反转后的头节点
	ListNode* last = reverseList(head->next);
	// 反转
	head->next->next = head;
	head->next = NULL;
	return last;
}


// 反转双链表
ListNode* reverse(ListNode* head){
	ListNode* prev = NULL;
	ListNode* curr = head;
	while(curr != NULL){
		curr->prev = curr->next;
		curr->next = prev;
		prev = curr;
		curr = curr.prev;
	}
	return prev;
}

打印两个有序链表的公共部分

// 谁小谁移动，相同打印并移动，有一个越界停。
void printPublic(ListNode* head1, ListNode* head2){
	ListNode* p1 = head1;
	ListNode* p2 = head2;
	while(p1 != NULL && p2 != NULL){
		if(p1->val < p2->val){
			p1 = p1->next;
		}else if(p1->val > p2->val){
			p2 = p2->next;
		}else{
			cout << p1->val << endl;
			p1 = p1->next;
			p2 = p2->next;
		}
	}
}

判断回文链表

// leetcode-234
// 1、辅助栈
bool isPalindrome(ListNode* head) {
	stack s;
	ListNode* p = head;
	while(p!=NULL){
		s.push(p->val);
		p = p->next;
	}
	p = head;
	while(p!=NULL){
		if(s.top() != p->val){
			return false;
		}
		s.pop();
		p = p->next;
	}
	return true;
}
// 2、快慢指针
ListNode* reverse(ListNode* head){
	ListNode* prev = NULL;
	ListNode* curr = head;
	ListNode* next = head;
	while(curr!=NULL){
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}
bool isPalindrome(ListNode* head) {
	if(head == NULL || head->next == NULL){
		return true;
	}
	ListNode* slow = head;
	ListNode* fast = head;
	while(fast.next!=NULL && fast->next->next!=NULL){
		// 慢指针一个一个走，快指针走双倍
		// 如果链表长度是奇数，最后slow走到中间，fast走到end
		// 如果链表长度是偶数，最后slow走到中间后一个，fast走到end+1（null）
		slow = slow->next;
		fast = fast->next->next;
	}
	// 链表长度是奇数，slow还要往后走一个(正中间就不比较了)
	if(fast!=NULL){
		slow = slow->next;
	}
	// 分成左右两块开始遍历
	ListNode* left = head;
	ListNode* right = reverse(slow);
	while(right!=NULL){
		if(left->val != right->val){
			return false;
		}
		left = left->next;
		right = right->next;
	}
	return true;
}

分割链表

// 定义六个指针变量sH/sT/eH/eT/bH/bT
// 1、分成<，=，>区版本 
ListNode* partition(ListNode* head, int val){
	ListNode* sH = NULL;
	ListNode* sT = NULL;
	ListNode* eH = NULL;
	ListNode* eT = NULL;
	ListNode* bH = NULL;
	ListNode* bT = NULL;
	ListNode* next = NULL;// 记录下一个节点
	while(head != NULL){
		next = head->next;
		// 摘下头节点
		head->next = null;
		// 连接
		if(head->val < val){
			if(sH == NULL){
				sH = head;
				sT = head;
			}else{
				sT->next = head;
				sT = head;
			}
		}else if(head->val == val){
			if(eH == NULL){
				eH = head;
				eT = head;
			}else{
				eT->next = head;
				eT = head;
			}
		}else{
			if(bH == NULL){
				bH = head;
				bT = head;
			}else{
				bT->next = head;
				bT = head;
			}
		}

		head = next;
	}
	// s区非空，连接s区和e区
	if(sT != NULL){
		sT->next = eH;
		// 判断e区是否为空，谁去连接b区
		eT = eT == NULL ? sT : eT;
	}
	// e区非空，连接e区和b区
	// 如果最后选择的去连接b区的不是空
	if(eT != NULL){
		eT->next = bH;
	}
	return sH != NULL ? sH : (eH != NULL ? eH : bH);
}
// 2、分成<，>=区版本
// leetcode-86
ListNode* partition(ListNode* head, int x) {
	ListNode* sH = NULL;
	ListNode* sT = NULL;
	ListNode* eH = NULL;
	ListNode* eT = NULL;
	ListNode* next = NULL;
	while(head != NULL){
		next = head->next;
		head->next = NULL;
		if(head->val < x){
			if(sH == NULL){
				sH = head;
				sT = head;
			}else{
				sT->next = head;
				sT = head;
			}
		}else{
			if(eH == NULL){
				eH = head;
				eT = head;
			}else{
				eT->next = head;
				eT = head;
			}
		}
		head = next;
	}
	if(sT != NULL){
		sT->next = eH;
	}
	return sH != NULL ? sH : eH;
}

复制带有随机指针的链表

// leetcode-138
// 1、哈希表（需要额外空间）
Node* copyRandomList(Node* head) {
	if(head == NULL) return head;
	unordered_map m;
	Node* curr = head;
	while(curr != NULL){
		// key旧节点，value新节点
		m[curr] = new Node(curr->val);
		curr = curr->next;
	}
	curr = head;
	while(curr != NULL){
		// 遍历旧节点，设置新节点的next和random
		m[curr]->next = m[curr->next];
		m[curr]->random = m[curr->random];
		curr = curr->next;
	}
	return m[head];
}
// 2、骚操作（不需要额外空间）
Node* copyRandomList(Node* head) {
	if(head == NULL) return head;
	Node* curr = head;
	Node* next = NULL;
	// 在老节点后面拷贝出一个新节点
	while(curr != NULL){
		next = curr->next;
		curr->next = new Node(curr->val);
		curr->next->next = next;
		curr = next;
	}
	curr = head;
	// 拷贝新节点的random
	Node* curCopy = NULL;// 分离新旧节点要用，不可省
	while(curr != NULL){
		next = curr->next->next;
		curCopy = curr->next;
		// 修改新节点的random
		curCopy->random = curr->random != NULL ? curr->random->next : NULL;
		curr = next;
	}
	Node* res = head->next;
	curr = head;
	// 分离新旧节点
	while(curr != NULL){
		next = curr->next->next;
		curCopy = curr->next;
		// 修改旧节点的next
		curr->next = next;
		// 修改新节点的next
		curCopy->next = next != NULL ? next->next : NULL;
		curr = next;
	}
	return res;
}

链表相交

// 求有环或无环链表相交节点
ListNode* getIntersectNode(ListNode* head1, ListNode* head2){
	if(head1 == NULL || head2 == NULL){
		return NULL;
	}
	ListNode* loop1 = getLoopNode(head1);
	ListNode* loop2 = getLoopNode(head2);
	if(loop1 == NULL && loop2 == NULL){
		return noLoop(head1, head2);
	}
	if(loop1 != NULL && loop2 != NULL){
		return bothLoop(head1, head2);
	}
	// 一个有环链表和一个无环链表是不可能相交的。
	return NULL;
}
// (1)求环的入节点
ListNode* getLoopNode(ListNode* head){
	if(head == NULL || head->next == NULL || head->next->next == NULL){
		return NULL;
	}
	// 如果链表有环，快慢指针会相遇；且快慢指针在环中转的圈数不会大于两圈，因为快指针比慢指针快了一倍。
	ListNode* slow = head->next;
	ListNode* fast = head->next->next;
	while(slow != fast){
		if(fast->next == NULL || fast->next->next == NULL){
			return NULL;
		}
		slow = slow->next;
		fast = fast->next->next;
	}
	// 当快慢指针相遇，快指针回到头，快慢指针一起一步一步走，相遇时则为环的入节点。
	fast = head;
	while(slow != fast){
		slow = slow->next;
		fast = fast->next;
	}
	return fast;
}
// (2)求两个无环链表的相交节点
ListNode* noLoop(ListNode* head1, ListNode* head2){
	if(head1 == NULL || head2 == NULL){
		return NULL;
	}
	ListNode* cur1 = head1;
	ListNode* cur2 = head2;
	int n = 0;// 两个链表长度差值
	while(cur1->next != NULL){
		n++;
		cur1 = cur1->next;
	}
	while(cur2->next != NULL){
		n--;
		cur2 = cur2->next;
	}
	// 走到结束不是同一个节点，则没有相交节点
	if(cur1 != cur2){
		return NULL;
	}
	// 让cur1指向长链表头
	cur1 = n>0 ? head1 : head2;
	cur2 = cur1 == head1 ? head2 : head1;
	n = abs(n);
	// 长链表走差值步数，走到和短链表长度相同处
	while(n != 0){
		n--;
		cur1 = cur1->next;
	}
	// 求相交节点
	while(cur1 != cur2){
		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	return cur1;
}
// (3)求两个有环链表的相交节点
ListNode* bothLoop(ListNode* head1, ListNode* loop1, ListNode* head2, ListNode* loop2){
	ListNode* cur1 = NULL;
	ListNode* cur2 = NULL;
	// 入环节点相同，化为求无环链表的相交节点
	if(loop1 == loop2){
		cur1 = head1;
		cur2 = head2;
		int n = 0;
		while(cur1->next != NULL){
			n++;
			cur1 = cur1->next;
		}
		while(cur2->next != NULL){
			n--;
			cur2 = cur2->next;
		}
		cur1 = n>0 ? head1 : head2;
		cur2 = cur1 == head1 ? head2 : head1;
		n = abs(n);
		while(n != 0){
			n--;
			cur1 = cur1->next;
		}
		while(cur1 != cur2){
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
		return cur1;
	}else{
	// 入环节点不同
		cur1 = loop1.next;
		while(cur1 != loop1){
			if(cur1 == loop2){
				return loop1;
			}
			cur1 = cur1->next;
		}
		return NULL;
	}
}

删除链表的倒数第N个节点

// leetcode-19
ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* vhead = new ListNode(0, head);
	ListNode* slow = vhead;
	ListNode* fast = vhead;
	// 快指针先走n步
	while(n != 0 && fast != nullptr){
		fast = fast->next;
		n--;
	}
	// 快指针再提前走一步（目的：让慢指针指向被删除节点的前一个）
	fast = fast->next;
	while(fast != nullptr){
		slow = slow->next;
		fast = fast->next;
	}
	// 删除
	slow->next = slow->next->next;
	return vhead->next;
}