链表重排，这种题一定要画图，画着画着思路就出来了边界条件：如果链表为空，或链表只有一个结点，或只有两个结点，直接返回head；设置双指针，p指向奇数结点，q指向偶数结点，同时设置一个evenhead结点指向q，作为偶数链的头结点1）让奇数结点指向偶数结点的下一个结点，同时p指针后移；2）让偶数结点指向奇数结点的下一个结点，同时q指针后移；3）以上两步做循环，直到奇数结点的下一个结点或偶数结点的下一个结点不存在，则退出 这里循环到最后有两种情况：1.是原链表有奇数个结点，此时，p指向最后一个结点，q指向空结点2.是原链表有偶数个结点，此时，p指向倒数第二个结点，q指向最后一个结点这两种情况，p都...

两种方法解决最小路径和的问题，一种方法是递归（超时），另一种方法是动态规划。其实动态规划和递归原理一样，都是将大问题转化为小问题求解的方法。本题的大小问题关系是：到nums[i][j]的最小路径和等于min(到上方nums[i-1][j]的最小和，到左方nums[i][j-1]的最小和） + nums[i][j]。 一、递归方法 class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector&l...

快慢指针找到链表中点，并将链表划分为前后两部分，然后将前后两部分合并。 class Solution { public: void reorderList(ListNode *head) { // 重排链表，可以用快慢指针找到链表的中间，并划分链表，然后将后边反转，然后进行两链表的合并操作 ListNode *slow = head, *fast = head; if (!head || !head->next || !head->next->next) return; while (fast->next && fast->next->nex...

用哈希表和栈解决括号序列有效性的问题先用哈希表来保存右括号和左括号的对应关系，设置一个栈保存左括号对括号序列进行遍历，如果是左括号，则进栈，如果是右括号，判断是否栈空，栈空或栈顶元素不等于相应的右括号，则括号序列不合法，return false;遍历完后，如果栈空，则有效，栈非空，说明栈中的左括号没有得到匹配的右括号，则括号序列无效。 class Solution { public: /** * * @param s string字符串 * @return bool布尔型 */ bool isValid(string s) { // write code here // s: "{}...

思路是遍历所有结点，构造一个数组，并反转数组，然后顺序与链表结点比较，只比较一半即可判断是否是回文结构 // 注意：快指针一次走两步，慢指针一次走一步，可以实现寻找链表的中间结点 // 空间复杂度为1的思路是通过快慢指针找到中间结点，然后将中间结点以后的结点反转，然后分别从两条链的链首开始遍历，判断相等进而判断是否是回文串 // 下边方法空间复杂度为O(n) #include <bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int val): val(v...

快慢指针法，要注意，慢指针指向结点的下一个结点才是要删除的结点，如果慢指针指向的结点是要删除的结点，那么就不好删除这个结点。 同样本题需要设置一个yummyhead结点来保证循环的一致性。 class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here // 删除链表的倒数第n个结点 // 用快慢指针法解决问题，先让快指针移动n次...

记住，是删除结点，所以至少需要三个指针，p、cur、q。可以设置一个yummyhead结点来保证循环的一致性，在循环的过程中，可以保证p结点和cur结点永远不相同，只比较cur和q即可。当cur和q相等时，用一个循环寻找第一个和cur不相等的q结点，让p结点指向q结点即可，这样就删除中间重复的cur结点，接下来如果q还存在，则指针后移。 class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // writ...

用yummyhead的非递归方法，先获取每组元素，如果够k个元素就反转。反转通过头插法来实现。 class Solution {public: /* * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ ListNode reverseKGroup(ListNode* head, int k) { // write code here // 每k个一组，进行反转  if (k == 0 || k == 1) return head; ListNode *yummyhead = new ListNode(-1); //...