双指针，每次对一个修改号进行比较 时间O(MAX(m,n)) 空间O(1) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 比较版本号 * @param version1 string字符串 * @param version2 string字符串 * @return int整型 */ int compare(string version1, string version2) { // writ...

二分法查找 如果mid的值大于mid+1，说明山峰在左边，令right = mid 如果mid的值小于mid+1，说明山峰在右边，令left = mid + 1 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int findPeakElement(vector<int>& nums) { /...

由于数组每行递增、每列递增，所以查找从右上方开始，向左向下移动，判断当前值与目标值的大小关系 时间复杂度O(m+n)，m为行数，n为列数 空间复杂度O(1) class Solution { public: bool Find(int target, vector<vector<int> > array) { int i = 0, j = array[0].size() - 1; while(i < array.size() && j >= 0){ if(array[i][j...

设置头节点方便处理 双指针，pre指向已处理好的链表的最后一个节点，p指向当前要判断的节点 while循环遍历链表，停止条件是p为空或p->next为空 当当前节点与下一节点相等时，while循环找到与当前节点不等的节点tmp，将pre指向tmp，当前节点更新为tmp，继续判断当前节点是否为重复节点 当当前节点与下一节点不等时，pre和p同时前进一位即可 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { // write code here ...

双指针，flag标记唯一数，cur标记当前位 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(!head) return head; // write code here ListNode* cur = head; ListNode* flag = head; while(cur){ if(flag == cur){//相等时，找下一个 cur = cur...

方法一 辅助数组 用两个数组分别储存odd和even位上的值，再修改原链表上节点的val class Solution { public: ListNode* oddEvenList(ListNode* head) { // write code here vector<int> odd; vector<int> even; ListNode* cur = head; int i = 1; while(cur){ if(i % 2 == 0...

快慢指针 在“判断链表是否有环”中，快慢指针同时从head出发 在“对单链表进行排序”中的归并排序，要找到链表的中点，则快指针从head->next出发，慢指针从head出发，这样，当快指针指向Null时，慢指针指向中心左边的节点（链表长度为偶数）或链表中点（链表长度为奇数） 一些值得复习的题 合并二叉树 递归合并两棵树，已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。 未完待续...

快慢指针 在“判断链表是否有环”中，快慢指针同时从head出发 在“对单链表进行排序”中的归并排序，要找到链表的中点，则快指针从head->next出发，慢指针从head出发，这样，当快指针指向Null时，慢指针指向中心左边的节点（链表长度为偶数）或链表中点（链表长度为奇数） 未完待续...

方法1 开辟新数组 空间复杂度：O(n) ---开辟了一个大小为n的数组储存元素 时间复杂度：O(nlogn) ---对数组里的元素进行排序 根据排序好的数组新建链表 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInLis...

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ...

双指针，先让p走到第n+1个节点处，让q指向头节点，然后p、q同时前进，当p走到链表尽头时，q正好走到倒数第n+1个节点，即要被删除的节点的前一个节点。删除节点。若删除的节点不是头节点，则返回头节点，否则返回头节点指向的下一个节点 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return L...

先判断有没有环，若有，设置两个指针，一个指向链表起点，一个指向相遇点，同时开始移动，相遇点即为环的入口节点 class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* meetNode = HasLoop(pHead); //先判断有没有环 if(!meetNode) return nullptr; //没有环，返回空 while(pHead != meetNode){ //两个指针，一个指向链表起点，一个指向相遇...

设置快慢指针，当快慢指针相遇时，说明链表中有环，一旦某个指针指向空，说明无环 如果先判断再位移，初始时fast和slow指向同一个节点，要单独讨论 if(fast->next->next && slow->next){ fast = fast->next->next; slow = slow->next; }else{ return false; } 改成先位移再判断，可以避免单独讨论 class Solution { public: ...

三指针pre、cur、rear 头和尾要单独考虑：头节点指向nullptr，尾节点指向pre class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(!pHead) return nullptr; if(!pHead->next) return pHead; ListNode* pre = pHead; ListNode* cur = pHead->next; ListNode* rear; pH...