1. 顺序表
说明：由于nums[src]等价于*(nums + src)，故以下将将下标计数器简化称作指针
1.1 移除元素
思路：
题目要求的空间复杂度O(1)的言外之意是不另外开辟数组空间，直接在原数组上进行删除元素的操作。一般情况下：如果只删除数组中的其中一个元素，只需将它后面的所有元素向前移动一位，将它覆盖即删除。而这道题有多个要删除的元素，核心思想也是一样的
“将它后面的所有元素向前移动一位”的前提条件是后面所有元素都不等于val(要删除的数)
那么有多个val的情况也是类似地，以val为分界线
如何达到分割数组的效果？
dst和src指针同时出发，当遇到val，dst停下，让src继续走直到不遇到val为止，然后再同时走，直到src(src走的快)遍历完数组。这相当于将等于val的元素跳过，分割数组的目的就是删除等于val的元素。注意：dst和src在同时走时，要将src的值赋给dst
- 循环终止条件：src遍历完数组
- 返回值：dst
int removeElement(int* nums, int numsSize, int val){ int dst = 0; int src = 0; while(src < numsSize) { if(nums[src] == val) { src++; } else { nums[dst] = nums[src]; dst++; src++; } } return dst; }
1.2 删除有序数组中的重复项
思路：
int removeDuplicates(int* nums, int numsSize){ int dst = 0; int src = 0; while(src < numsSize) { if(nums[dst] == nums[src]) { src++; } else { nums[++dst] = nums[src++];//注意这里是将src位置的值赋值给dst的下一个位置 } } return dst + 1; }
找到每个分界点，且将它们组成的区间内的元素删除，思路和上一题类似：dst记录覆盖后的位置，src找下一个分界点。当src找到分界点，将其值赋值给dst的下一个位置(因为dst当前的位置是相对于src的上一个分界点)，然后src继续找，直到遍历完数组。
- 循环终止条件：src遍历完数组
- 返回修改后的数组长度：dst+1(dst是下标，从0开始)
1.3 合并两个有序数组
思路：
这是归并排序的核心思想，前提是要比较的两个数组已经排好顺序
- 循环终止条件：至少有一个数组遍历完毕。实际上，这里num1一定会遍历完的，因为num1剩余的空间要存放num2
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ //都是下标 int end = nums1Size - 1; int end1 = m - 1; int end2 = n - 1; while(end1 >= 0 && end2 >= 0)//把小的放进去 { if(nums1[end1] > nums2[end2]) { nums1[end] = nums1[end1]; end--; end1--; } else { nums1[end] = nums2[end2]; end--; end2--; } } while(end2 >= 0)//num2可能有剩余元素 { nums1[end] = nums2[end2]; end--; end2--; } return nums1; }
1.4 轮转数组
思路：
这种轮转(左旋/右旋)的题，不论是轮转字符串、数组，都可以用这种思想：各部分逆置+整体逆置。
- 重点是用k找到分界线
- 逆置功能写成单独的函数
- 当k大于数组长度，将k模上长度即可
//逆置函数 void reverse(int* nums, int start, int end) { int left = start; int right = end - 1; while(left < right) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k){ k %= numsSize; if(k < numsSize) { reverse(nums, 0, numsSize - k);//前一部分 reverse(nums, numsSize - k, numsSize);//后一部分 reverse(nums, 0, numsSize);//整体 } }
1.5 数组形式的整数加法
2. 链表
2.1 移除链表元素
思路：
因为单向链表的局限性，只能用三个指针维护要删除节点的前中后三个节点
- 三指针同时迭代的条件：cur->val != val
- 让prev指向next之前，要先用cur得到next。并且要先free掉cur当前的值再更新cur的位置
- 删除的节点若为第一个节点，则需要更新head的地址
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { if(cur->val == val) { struct ListNode* next = cur->next; //如果要删除的是第一个节点 if(prev == NULL)//cur指向head，prve为空 { free(cur); head = next;//更新第一个节点 cur = head;//迭代cur } else { prev->next = next;//迭代prev free(cur); cur = next;//迭代cur } } else { prev = cur; cur = cur->next;//迭代 } } return head; }
注：其实next指针不用每次都更新它，因为只有在碰到要删除的节点要需要用到它，所以这里将最后一个else语句中的next迭代放到了第二个if语句中
2.2 反转链表
思路:遍历，反向
此思路比较简单，同样是三指针同时迭代，为了可读性，这里将要返回的指针命名为newhead
struct ListNode* reverseList(struct ListNode* head){ struct ListNode* cur = head; struct ListNode* newhead = NULL; while(cur) { struct ListNode* next = cur->next;//保存cur的下一个节点 cur->next = newhead;//cur逆指 newhead = cur//更新 cur = next;//更新 } return newhead; }
2.3 链表的中间结点
思路：
快慢指针是一个经典方法，十分巧妙。接下来会介绍快慢指针的更多用法。
- 奇数个节点循环终止的条件是迭代到最后一个节点，偶数个节点循环终止的条件是迭代到NULL(即最后一个节点的next)。所以循环终止的条件有两个。
struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast = head; struct ListNode* slow = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
为什么循环条件是&&而不是||？
2.4 链表中倒数第k个结点
思路：
让快指针先走k步，作用是锁定了两指针之间的距离
- 注意判断链表是否为空和k是否大于链表长度
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { int len = 0; struct ListNode* fast = pListHead; struct ListNode* slow = pListHead; struct ListNode* cur = pListHead; while(cur)//计算链表的长度 { len++; cur = cur->next; } if(len == 0 || k > len) { return NULL; } while(k--)//让fast先走k步 { fast = fast->next; } while(fast)//让快慢指针同时走 { fast = fast->next; slow = slow->next; } return slow; }
2.5 合并两个有序链表
思路：
这是归并排序的核心思想
- 新链表的每次更新，都要更新cur
- 注意链表为空的情况。一共有三种情况：只有list1为空；只有list2为空；全为空。如何处理？
- 若原链表长度不同，最后一定会有剩下的节点，只需将它们链接到新链表的当前位置即可。同样需要判断是哪一个链表还剩。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* l1 = list1; struct ListNode* l2 = list2; struct ListNode* listhead = NULL; //判断链表为空 if(l1 == NULL) { return l2; } if(l2 == NULL) { return l1; } //把第一个val小的节点作为listhead struct ListNode* cur = NULL;//迭代指针变量 if(l1->val < l2->val) { listhead = cur = l1; l1 = l1->next; } else { listhead = cur = l2; l2 = l2->next; } while(l1 && l2) { if(l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } //此时至少有一个走完，将剩下的连接上 if(l1 == NULL) { cur->next = l2; } else { cur->next = l1; } return listhead; }
2.6 链表分割
注：头节点(哨兵位节点)和第一个节点不同，头节点仅存放了第一个节点的地址，不存放数据，第一个节点才是真正有数据的节点。可以理解为头节点就是一个代号，代表着这个链表
思路：
其核心思路为：先分组，再链接。
- 链接时注意不要链接到要free掉的节点
- free掉开辟的内存
ListNode* partition(ListNode* pHead, int x) { struct ListNode* cur = pHead; struct ListNode* greaterHead, *greaterTail, *lesstail, *lesshead; //为两个头节点开辟内存 greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); lesstail = lesshead = (struct ListNode*)malloc(sizeof(struct ListNode)); lesstail->next = NULL; greaterTail->next = NULL; //分组 while (cur) { if(cur->val < x) { lesstail->next = cur; lesstail = lesstail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next;//注意迭代！ } lesstail->next = greaterHead->next;//跳过头节点再链接 greaterTail->next = NULL; pHead = lesshead->next;//更新pHead free(lesshead); free(greaterHead); return pHead; }
2.7 链表的回文结构
思路：
为什么会出现最后那个巧合？
因为将后半部分逆置时并没有处理中间节点前面的节点(这里是2)，也就是说，倒置完以后，2依然是指向3的。这个巧妙的巧合就免去了当链表节点个数为奇数时，还要增加一系列条件判断，例如节点为个数奇数时，cur2后半部分的最后一个节点不需要比较等(因为对称轴没法跟谁比)。
class PalindromeList { public: bool chkPalindrome(ListNode* A) { ListNode* fast = A; ListNode* slow = A; ListNode* cur1 = A; ListNode* cur2 = NULL; while(fast->next && fast)//找中 { fast = fast->next->next; slow = slow->next; } //此时slow指向中间节点 while(slow)//逆置后一半 { ListNode* next = slow->next; slow->next = cur2; cur2 = slow; slow = next; } //此时cur2是后半部分的第一个节点 while(cur1 && cur2) { if(cur1->val != cur2->val) { return false; } else//迭代 { cur1 = cur1->next; cur2 = cur2->next; } } //当前面 return true; } };
2.8 相交链表
思路：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode * cur1 = headA; struct ListNode * cur2 = headB; struct ListNode * cur11 = headA; struct ListNode * cur22 = headB; if(headA == NULL || headB == NULL) { return NULL; } int len1 = 0, len2 = 0; //计算链表的长度 while(cur1) { len1++; cur1 = cur1->next; } while(cur2) { len2++; cur2 = cur2->next; } int k = abs(len1 - len2);//得出链表长度之差的绝对值 if(len1 > len2) { while(k--) { cur11 = cur11->next; } } else { while(k--) { cur22 = cur22->next; } } //此时两链表处于同一起始点（距离交点的长度） while(cur11 && cur22) { if(cur11 != cur22) { cur11 = cur11->next; cur22 = cur22->next; } else { return cur22; } } return NULL; }
更新日志
4/15/2022 man9o
