< n) dfs(n, ln + 1, rn, path + "(");if(ln > rn && rn < n) dfs(n, ln, rn + 1, path + ")");}}};
24. 两两交换链表中的节点
思想
整个过程如图所示 ， 涉及到头节点变化的题目都可以通过创建虚拟头节点提供便利 。交换过程需要考虑先后问题
链表题注意事项：
以下错误原因 ， 链表的下一个节点是否为空都需要有一个判断 ， 否则就会出现这个错误
runtime error: member access within null pointer of type 'ListNode'
/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode() : val(0), next(nullptr) {}*ListNode(int x) : val(x), next(nullptr) {}*ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:ListNode* swapPairs(ListNode* head) {auto dummy = new ListNode(-1), tail = dummy;dummy->next = head;while(tail->next && tail->next->next) {auto h1 = tail->next, h2 = h1->next;h1->next = h2->next;h2->next = h1;tail->next = h2;tail = h1;}return dummy->next;}};
25. K 个一组翻转链表
思想
本题和上一题思路非常相似 ， 变成了翻转k个数 。
第一步我们还是创建虚拟头节点通过遍历的方式判断后续是否含有k个节点 ， 不足则不进行翻转操作整个翻转的过程我们可以分为三步
a. 第一步完成k个节点内部指针的反向指针（注意翻转变化的顺序）
b. 第二步虚拟头节点下一个指针改变
c. 第三步k个节点的最后一个节点指针改变指针改变需要三个指针 ， 通过下图帮助理解
/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode() : val(0), next(nullptr) {}*ListNode(int x) : val(x), next(nullptr) {}*ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/class Solution {public:ListNode* reverseKGroup(ListNode* head, int k) {//注意提前保存后续要使用到的节点ListNode* dummy = new ListNode(-1);dummy->next = head;for(ListNode* h0 = dummy;;) {//遍历查看是否含有k个节点ListNode* h00 = h0;for(int i = 0; i < k && h00; i++) h00 = h00->next;if(!h00) break;//含有k个元素 ， 需要通过赋值的两个指针进行链表内部的翻转auto h1 = h0->next, h11 = h0->next, h2 = h1->next;//一共k个元素需要进行k - 1次翻转操作for(int i = 0; i < k - 1; i++) {auto h3 = h2->next;h2->next = h1;h1 = h2, h2 = h3;}h0->next = h1;h11->next = h2;h0 = h11;}return dummy->next;}};
26. 删除有序数组中的重复项
思想
这其实就是一个函数 ， 我们就去判断一个数和它前一个数是否重复 ， 比较简单直接上代码
class Solution {public:int removeDuplicates(vector& nums) {int cnt = 0;for(int i = 0; i < nums.size(); i++) {if(!i || nums[i] != nums[i - 1]) nums[cnt++] = nums[i];}return cnt;}};
27. 移除元素
思想
和上面题目思想高度类似 。通过cnt变量记录应该放置在数组的什么位置 ， 比较简单代码如下：
class Solution {public:int removeElement(vector& nums, int val) {int cnt = 0;for(int i = 0; i < nums.size(); i++) {if(nums[i] != val)nums[cnt++] = nums[i];}return cnt;}};
28. 找出字符串中第一个匹配项的下标
这道题目就是KMP算法的内容 ， 需要回顾一下KMP的知识 。
class Solution {public:int strStr(string haystack, string needle) {if(needle.empty()) return 0;int n = haystack.size(), m = needle.size();int ne[m];//预处理needlene[0] = -1;for(int i = 1, j = -1; i