这两天身体不舒服，没有按照原定计划完成，算是整理下思绪，希望能更高的效率做题把.
today's mission
1-28
leetcode 数字有关运算题汇总：这类题目在面试中还是出现频率很高的。
2 . add two numbers
这个题目如果方法选的不好，思路不清晰，做起事是很痛苦的！！！一开始，我想着把 l1 和 l2的数加在一起然后放在l1的值里面，不加任何辅助的指针，但是这样做的坏处是，当L2 比 l1长，l1到达了NULL， l1再也不能放值了，这样的问题如果不用一个辅助指针根本无法处理啊！既然需要用到辅助指针，为什么不想Merge two sorted list那样，用两个辅助指针， dummy head + cur（TAIL）， 这样可以非常方便地处理两个list不等长的结果。
时间复杂度： O（n+m）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if (l1 == NULL && l2 == NULL) return NULL;
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
int cnt = 0;
ListNode* head = new ListNode(0);
ListNode* cur = head;
while (l1 != NULL || l2 != NULL) {
if (l1 != NULL && l2 != NULL) {
int tmp = (l1->val + l2->val + cnt) % 10;
cnt = (l1->val + l2->val + cnt) / 10;
l1->val = tmp;
cur->next = l1;
cur = l1;
l1 = l1->next;
l2 = l2->next;
} else if (l1 != NULL) {
int tmp = (l1->val + cnt) % 10;
cnt = (l1->val + cnt) / 10;
l1->val = tmp;
cur->next = l1;
cur = l1;
l1 = l1->next;
} else if (l2 != NULL) {
int tmp = (l2->val + cnt) % 10;
cnt = (l2->val + cnt) / 10;
l2->val = tmp;
cur->next = l2;
cur = l2;
l2 = l2->next;
}
}
if (cnt == 1) {
cur->next = new ListNode(1);
}
return head->next;
}
};
7. reverse integer
这个题目要注意一点是， 一个数reverse过程中可能会出现overflow的情况， 对overflow的处理是， 如果是负数，返回 MIN， 如果是正数， 返回MAX，
关键是如何去判断这个数在reverse过程中是否overflow。sum的计算公式是： sum * 10 + n , 要使在计算过程中不越界， sum * 10 + n <= INT_MAX, 所以这就是是否越界的判断公式。
class Solution {
public:
int reverse(int x) {
int flag = false;
if (x < 0 ) flag = true;
x = abs(x);
int sum = 0;
while (x) {
int n = x % 10;
int c = x / 10;
if (sum <= (INT_MAX - n) / 10) {
sum *= 10;
sum += n;
} else {
return 0;
}
x = c;
}
if (flag) return sum*(-1);
return sum;
}
};
关键是如何去判断这个数在reverse过程中是否overflow。sum的计算公式是： sum * 10 + n , 要使在计算过程中不越界， sum * 10 + n <= INT_MAX, 所以这就是是否越界的判断公式。
class Solution {
public:
int reverse(int x) {
int flag = false;
if (x < 0 ) flag = true;
x = abs(x);
int sum = 0;
while (x) {
int n = x % 10;
int c = x / 10;
if (sum <= (INT_MAX - n) / 10) {
sum *= 10;
sum += n;
} else {
return 0;
}
x = c;
}
if (flag) return sum*(-1);
return sum;
}
};
8. string to integer
这个题目虽然简单，但是还是属于特别容易出错的题目， 在开始做之前，应该先跟面试官弄清楚转换的规则是什么， 比如这个题目里面规定的是： 1. 从第一个非空格的char开始转换 2. 如果invalid string ， 返回 0， 否则返回具体的值， 注意overflow的情况下返回INT_MIN, INT_MAX . 3. valid string是指+、-、digit, 并且要求， 只能有一个符号位，并且紧跟着数字，其他情况下都是invalid。
这个题目逻辑最清晰的写法是： 将遇到第一个+, -或者digit的情况提出来利用辅助函数 convert来进行计算第一个可能valid的string， 在convert里函数只能处理digit的字符， 其他字符，return 0;
class Solution {
private:
int convert(string str, int idx, bool positive) {
int rst = 0;
for (int i = idx; i < str.size(); i++) {
if (isdigit(str[i])) {
if (rst <= (INT_MAX - (str[i] - '0')) / 10) {
rst *= 10;
rst += str[i] - '0';
} else {
rst = INT_MAX;
return positive ? rst : INT_MIN;
}
} else {
break;
}
}
return positive ? rst : -rst;
}
public:
int myAtoi(string str) {
if (str.size() == 0) return 0;
int rst = 0;
bool positive = true;
for (int i = 0; i < str.size(); i++) {
if (str[i] == ' ') { //trim space
continue;
} else if (str[i] == '+') {
positive = true;
rst = convert(str, i+1, positive);
break;
} else if (str[i] == '-') {
positive = false;
rst = convert(str, i+1, positive);
break;
} else if (isdigit(str[i])) {
rst = convert(str, i, positive);
break;
} else {
break;
}
}
return rst;
}
};
这个题目逻辑最清晰的写法是： 将遇到第一个+, -或者digit的情况提出来利用辅助函数 convert来进行计算第一个可能valid的string， 在convert里函数只能处理digit的字符， 其他字符，return 0;
class Solution {
private:
int convert(string str, int idx, bool positive) {
int rst = 0;
for (int i = idx; i < str.size(); i++) {
if (isdigit(str[i])) {
if (rst <= (INT_MAX - (str[i] - '0')) / 10) {
rst *= 10;
rst += str[i] - '0';
} else {
rst = INT_MAX;
return positive ? rst : INT_MIN;
}
} else {
break;
}
}
return positive ? rst : -rst;
}
public:
int myAtoi(string str) {
if (str.size() == 0) return 0;
int rst = 0;
bool positive = true;
for (int i = 0; i < str.size(); i++) {
if (str[i] == ' ') { //trim space
continue;
} else if (str[i] == '+') {
positive = true;
rst = convert(str, i+1, positive);
break;
} else if (str[i] == '-') {
positive = false;
rst = convert(str, i+1, positive);
break;
} else if (isdigit(str[i])) {
rst = convert(str, i, positive);
break;
} else {
break;
}
}
return rst;
}
};
9. palindrome number
这个题目也是依据palindrome number的思想， 对数的首尾数字进行判断， 唯一一个需要注意的地方是， 在计算过程中count可能溢出，因为count在后面 count = count/10的操作， 可能会造成溢出， eg： x = 1000000001， 10位数，*10, 11位数，就溢出了。一般机器能handle的最大int值 2147483647，10位， 11位的数就直接溢出了。
class Solution {
private:
bool helper(int x, long count) {
while (count > 1) {
int last = x % 10;
int first = x/count;
if (last != first) return false;
x = (x % count)/10;
count = count/100;
}
return true;
}
public:
bool isPalindrome(int x) {
if (x < 0) return false;
long count = 1;
int tmp = x;
while (tmp) {
tmp = tmp/10;
count = count * 10;
}
count /= 10;
return helper(x, count);
}
};
class Solution {
private:
bool helper(int x, long count) {
while (count > 1) {
int last = x % 10;
int first = x/count;
if (last != first) return false;
x = (x % count)/10;
count = count/100;
}
return true;
}
public:
bool isPalindrome(int x) {
if (x < 0) return false;
long count = 1;
int tmp = x;
while (tmp) {
tmp = tmp/10;
count = count * 10;
}
count /= 10;
return helper(x, count);
}
};
12. Interger to Roman
13. Roman to Integer
29： divide two integers
这个题目的算法还是记住比较好，用的其实是 a/b -> a = b * 2 ^n + b * 2^(n-1) +.....+ b* 2^0;
每次通过移位操作计算n， 但是要注意INT_MIN如果直接利用abs转换成负数的话，会造成溢出，所以我们需要先把INT_MIN --> long long的范围内再进行转换成正数。还要注意corner case的判断： 当 dividend 是INT_MIN, divisor 是 -1的时候， 会造成溢出，直接返回INT_MAX；
43. multiply strings
每次做这种大数乘的题目就很慌张，有点怕，不太会做这种数学题，但是大数乘的题目在面试中还是经常考到的，不会做也要学会多做做就不怕了。
这个题目由于数字都是用string表示的，所以最好先把这些string都reverse一下，然后需要一个额外的空间来存储乘法相对应位的累加结果，然后在对这些累加的结果进行处理，比如需要往前进位啥的，最后由于一开始开辟的是最大的可能空间，如果最后不需要那么多的话，会有前导0的出现， 所以最后我们需要去掉前导0。 用到了string erase的函数。
class Solution {
public:
string multiply(string num1, string num2) {
string rst = "";
if (num1.size() == 0 || num2.size() == 0) return rst;
//reverse two strings
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
//get sum in each position
int M[num1.size() + num2.size()] = {0};
for (int i = 0; i < num1.size(); i++) {
for (int j = 0; j < num2.size(); j++) {
M[i+j] += (num1[i] - '0') * (num2[j]-'0');
}
}
//dealing with these sums
for (int i = 0; i < num1.size() + num2.size(); i++) {
int digit = M[i] % 10;
int cnt = M[i]/10;
if (i+1 < num1.size()+num2.size()) {
M[i+1] += cnt;
}
char tmp = (digit + '0');
rst += tmp;
}
reverse(rst.begin(), rst.end());
int i = 0;
while (i < rst.size()-1 && rst[i] == '0') i++;
rst.erase(0,i);
return rst;
}
};
每次做这种大数乘的题目就很慌张，有点怕，不太会做这种数学题，但是大数乘的题目在面试中还是经常考到的，不会做也要学会多做做就不怕了。
这个题目由于数字都是用string表示的，所以最好先把这些string都reverse一下，然后需要一个额外的空间来存储乘法相对应位的累加结果，然后在对这些累加的结果进行处理，比如需要往前进位啥的，最后由于一开始开辟的是最大的可能空间，如果最后不需要那么多的话，会有前导0的出现， 所以最后我们需要去掉前导0。 用到了string erase的函数。
class Solution {
public:
string multiply(string num1, string num2) {
string rst = "";
if (num1.size() == 0 || num2.size() == 0) return rst;
//reverse two strings
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
//get sum in each position
int M[num1.size() + num2.size()] = {0};
for (int i = 0; i < num1.size(); i++) {
for (int j = 0; j < num2.size(); j++) {
M[i+j] += (num1[i] - '0') * (num2[j]-'0');
}
}
//dealing with these sums
for (int i = 0; i < num1.size() + num2.size(); i++) {
int digit = M[i] % 10;
int cnt = M[i]/10;
if (i+1 < num1.size()+num2.size()) {
M[i+1] += cnt;
}
char tmp = (digit + '0');
rst += tmp;
}
reverse(rst.begin(), rst.end());
int i = 0;
while (i < rst.size()-1 && rst[i] == '0') i++;
rst.erase(0,i);
return rst;
}
};
67. add binary
1. 2 SUM
2sum 有很多变形的，比如： 有的题目要求找出一对具体的两个元素，有的题目要求找出一对Index, 有的题目要求找出所有的配对的元素，有的题目要求找出所有配对的Index,
如果要求找出所有配对的Index, 最好是不要对之前的元素排序，直接用hashmap的方法来做， 因为排了序之后Index的顺序都改变了。 如果是要求找出具体的元素，两种方法都是可以做的，看面试官要求是什么。
15. 3 SUM
3sum 这个题目还是有很多陷阱，两种方法：hashmap/sort
sort : 因为题目里面是有duplicates elements的，所以在每一步移动一个index的时候，都必须要先看新的index指向的元素是否与之前的元素相等。在去duplicate的时候要注意，先移动index，再去处理duplicate， 防止没有duplicate的时候，没有移动任何Index, 造成死循环。
hashmap: 因为这个题目里面含有重复元素， 所以利用hashmap不太好处理duplicate， 而且不管用hashmap还是sort，时间复杂度最高还是O（n^2）, 排序不会影响时间复杂度。
所以 对于含有duplicates的题目，还是用sort的方法比较好。
16. 3SUM closest
这个题目和3 sum的解法是相同，不同的是每次每次移动任何一个指针，都要计算一下当前的差值，并且维护一个最小差值，最后那个最小差值对应的sum就是结果。
要想提高程序的运行速度，我们需要把重复的运算和操作合并，使其只运行一次。
18. 4 SUM --> K SUM
如果4 SUM继续利用3 SUM的方法进行的话， 时间复杂度是O（n^3）
但是联想从2SUM --> K SUM的推广的方法，我们是可以利用2SUM来解的， 我们可以先得到所有2 SUMpair， 并且存在hashmap中，然后再进行2 sum， 时间复杂度是O（n^2）， 算法的思想很简单，但是由于可能有重复的pair出现，所以有很多的case 需要考虑。
3. longest substring without repeating character
这个题目是string里面 sliding window + contain duplicates的结合， 一开始想到 用 unordered_set 来处理发现duplicates的情况，后来有注意到unordered_set作用的对象是char, 对于 256 ASCII字符来说可以使用 256 size的array 来代替 set。这样可以提高set里面erase的复杂度。 时间复杂度： O(n * 2)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
//unordered_set<char> iset;
int iset[256] = {0};
int left = 0;
int right = 0;
int gmax = 0;
for (; right < s.size(); right++) {
if (iset[s[right]] == 0) {
iset[s[right]]++;
gmax = max(gmax, right-left+1);
} else {
while (s[left] != s[right]) {
iset[s[left]] = 0;
left++;
}
left++;
}
}
return gmax;
}
};
4. median of two sorted array
5. longest palindrome substring
M1: use 2D dp, check if palindrome and update the maximum length
只是这种简单的dp每次都没有一次性写对，而且每次都是把j == i+1 写成了 j = i+1， 每次还看半天都不能发现的bug ！！！！
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() == 0) return s;
bool M[s.size()][s.size()];
int gmax = 0;
int left = 0;
for (int i = s.size()-1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if ((j == i) || ((s[i] == s[j]) && (j == i+1 || M[i+1][j-1]))) {
M[i][j] = true;
if (gmax < j-i+1) {
gmax = j - i +1;
left = i;
}
} else {
M[i][j] = false;
}
}
}
return s.substr(left, gmax);
}
};
时间复杂度： O(n^2) 空间复杂度： O（n^2）
M2：专门解决 longest palindrome string 问题的一个算法是 : Manacher's algorithm, 时间复杂度O（n）， 非常巧妙的一个算法，
M1: use 2D dp, check if palindrome and update the maximum length
只是这种简单的dp每次都没有一次性写对，而且每次都是把j == i+1 写成了 j = i+1， 每次还看半天都不能发现的bug ！！！！
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() == 0) return s;
bool M[s.size()][s.size()];
int gmax = 0;
int left = 0;
for (int i = s.size()-1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if ((j == i) || ((s[i] == s[j]) && (j == i+1 || M[i+1][j-1]))) {
M[i][j] = true;
if (gmax < j-i+1) {
gmax = j - i +1;
left = i;
}
} else {
M[i][j] = false;
}
}
}
return s.substr(left, gmax);
}
};
时间复杂度： O(n^2) 空间复杂度： O（n^2）
M2：专门解决 longest palindrome string 问题的一个算法是 : Manacher's algorithm, 时间复杂度O（n）， 非常巧妙的一个算法，
6. zigzag conversion
纯粹的数学题
10. regular expression matching
11. container with most water
这个题目感觉是简化版的trapping rain water, 以线作为板子，只需要找到两根线和x轴组成的区域面积最大， 也是histogram 板子，短板原理， 两个pointer, 分别指向首尾两端， 谁短移动谁，并且维护最大面积， 这个题目这样其实就是每次都计算出每块短板能组成的最大面积。
follow up: 42. trapping rain water
trapping rain water 比 container with most water处理上要难一些，但是两题的思路是相同的，都是利用两个指针指向两端，然后移动短板，这个题目在移动短板的时候进行的处理操作是， 对每一个短板计算能储存水的量， 这个短板能储存水的量 = maxLeft - height[left] or maxRight - height[right], 需要维护三个值，一个是左边板子的最大高度， 右边板子的最大高度， 以及sum。
14: longest common prefix
这个题目求公共前缀， 以第一个string为基准，一个字符一个字符地比较其他字符串相应位置的字符，如果都相同，那么说明找到了一个common char, 加在 rst的尾部。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string rst = "";
if (strs.size() == 0) return rst;
if (strs.size() == 1) return strs[0];
for (int i = 0; i < strs[0].size(); i++) {
for (int j = 1; j < strs.size(); j++) {
if (i >= strs[j].size() || strs[0][i] != strs[j][i]) return rst;
}
rst += strs[0][i];
}
return rst;
}
};
17： letter combinations of a phone number
这个题目一看输出所有的结果，肯定是dfs来解题， dfs注意树的层数, 每一层什么含义和每一层的分支。
eg: 23 :
position0 : a b c
/|\ /|\ /|\
position 1: def def......
19. remove nth node from linked list
这个题目很简单，但是还是写了两遍才写对。 要注意两点，首先这个题目可能head会被remove, 所以保险起见，我们加一个dummy node， 其次， 当找到了要删的节点位置后， pre->next = slow->next， 这个是逻辑公式，每次写都认为是 pre->next = fast, 其实这个逻辑式一看就是错的，因为fast并不是就是在slow之后啊， 很简单的例子，比如 n= 5, 那么fast 和 slow 相隔就是5个node的距离了。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL) return NULL;
ListNode* slow = head;
ListNode* fast = head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
while (n > 0) {
n--;
fast =fast->next;
}
while (fast) {
fast = fast->next;
pre = slow;
slow = slow->next;
}
pre->next = slow->next;
return dummy->next;
}
};
20： valid parentheses
这个题目判断括号对是否匹配， 用一个stack去匹配。
对这个stack进行push, pop只有两种情况， 当 stack不为空， 并且stack的 top 和 char c 可以匹配的时候，可以从stack里pop出一个元素，其他情况下，都把元素push到stack中。
21. merge two sorted list
23. merge k sorted list
merge two sorted list 现在可以很熟练地写出来，但是merge k sorted list 才是重点， 这个题目从 2 -->k的扩展，体现了两种基本的思想： M1 ： use priority_queue to handle k object, sort, initial states and expand rules and do it in a breadth first search way. M2: divide and conquer, iteratively apply 2 way method to get the k way method. you need to think the rules to get k. (DIVIDE AND CONQUER is generally used in k way questions and always works).
time complexity: O(n * k * logn) because every list node is pushed and popped from priority_queue , space complexity: M1:O(n*k) M2: O(1)
22. generate parentheses
利用dfs 就可以解决， 很简单。
24. swap nodes in pair
这个题目属于比较复杂的list里面的指针操作了，在进行比较复杂的指针操作的时候要注意， 必要的时候一定要记得断掉已经不存在的链接，或者无效的链接，否则，list会进入一个cycle, 比如这个题目里面每次 pre->next = NULL, cur node 和 next node之间的这个链接应该不再存在。要注意区分偶数个和奇数个nodes的情况。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur && cur->next) {
ListNode* next = cur->next;
ListNode* nnext = next->next;
next->next = cur;
pre->next = next;
pre = cur;
pre->next = NULL;
cur = nnext;
}
if (cur) {
pre->next = cur;
}
return dummy->next;
}
};
25. reverse nodes in k-group
这个题目是上一个的2 --> k的拓展， 对于这个题目采取的做法是在2上进行修改， 其实整体上指针的操作逻辑是没有改变的，1. 指针操作还是需要小心，可以避免区别奇数和偶数的情况，可以统一处理。 2. tail 在
这个题目还是有很多细节要注意，一遍不容易写对。
26. remove duplicates in sorted array
27. remove element
这两个题目都是属于array的操作，也可以应该在string 的操作上，
28. implement strStr()
纯粹的数学题
10. regular expression matching
11. container with most water
这个题目感觉是简化版的trapping rain water, 以线作为板子，只需要找到两根线和x轴组成的区域面积最大， 也是histogram 板子，短板原理， 两个pointer, 分别指向首尾两端， 谁短移动谁，并且维护最大面积， 这个题目这样其实就是每次都计算出每块短板能组成的最大面积。
follow up: 42. trapping rain water
trapping rain water 比 container with most water处理上要难一些，但是两题的思路是相同的，都是利用两个指针指向两端，然后移动短板，这个题目在移动短板的时候进行的处理操作是， 对每一个短板计算能储存水的量， 这个短板能储存水的量 = maxLeft - height[left] or maxRight - height[right], 需要维护三个值，一个是左边板子的最大高度， 右边板子的最大高度， 以及sum。
14: longest common prefix
这个题目求公共前缀， 以第一个string为基准，一个字符一个字符地比较其他字符串相应位置的字符，如果都相同，那么说明找到了一个common char, 加在 rst的尾部。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string rst = "";
if (strs.size() == 0) return rst;
if (strs.size() == 1) return strs[0];
for (int i = 0; i < strs[0].size(); i++) {
for (int j = 1; j < strs.size(); j++) {
if (i >= strs[j].size() || strs[0][i] != strs[j][i]) return rst;
}
rst += strs[0][i];
}
return rst;
}
};
17： letter combinations of a phone number
这个题目一看输出所有的结果，肯定是dfs来解题， dfs注意树的层数, 每一层什么含义和每一层的分支。
eg: 23 :
position0 : a b c
/|\ /|\ /|\
position 1: def def......
19. remove nth node from linked list
这个题目很简单，但是还是写了两遍才写对。 要注意两点，首先这个题目可能head会被remove, 所以保险起见，我们加一个dummy node， 其次， 当找到了要删的节点位置后， pre->next = slow->next， 这个是逻辑公式，每次写都认为是 pre->next = fast, 其实这个逻辑式一看就是错的，因为fast并不是就是在slow之后啊， 很简单的例子，比如 n= 5, 那么fast 和 slow 相隔就是5个node的距离了。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (head == NULL) return NULL;
ListNode* slow = head;
ListNode* fast = head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
while (n > 0) {
n--;
fast =fast->next;
}
while (fast) {
fast = fast->next;
pre = slow;
slow = slow->next;
}
pre->next = slow->next;
return dummy->next;
}
};
20： valid parentheses
这个题目判断括号对是否匹配， 用一个stack去匹配。
对这个stack进行push, pop只有两种情况， 当 stack不为空， 并且stack的 top 和 char c 可以匹配的时候，可以从stack里pop出一个元素，其他情况下，都把元素push到stack中。
21. merge two sorted list
23. merge k sorted list
merge two sorted list 现在可以很熟练地写出来，但是merge k sorted list 才是重点， 这个题目从 2 -->k的扩展，体现了两种基本的思想： M1 ： use priority_queue to handle k object, sort, initial states and expand rules and do it in a breadth first search way. M2: divide and conquer, iteratively apply 2 way method to get the k way method. you need to think the rules to get k. (DIVIDE AND CONQUER is generally used in k way questions and always works).
time complexity: O(n * k * logn) because every list node is pushed and popped from priority_queue , space complexity: M1:O(n*k) M2: O(1)
22. generate parentheses
利用dfs 就可以解决， 很简单。
24. swap nodes in pair
这个题目属于比较复杂的list里面的指针操作了，在进行比较复杂的指针操作的时候要注意， 必要的时候一定要记得断掉已经不存在的链接，或者无效的链接，否则，list会进入一个cycle, 比如这个题目里面每次 pre->next = NULL, cur node 和 next node之间的这个链接应该不再存在。要注意区分偶数个和奇数个nodes的情况。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur && cur->next) {
ListNode* next = cur->next;
ListNode* nnext = next->next;
next->next = cur;
pre->next = next;
pre = cur;
pre->next = NULL;
cur = nnext;
}
if (cur) {
pre->next = cur;
}
return dummy->next;
}
};
25. reverse nodes in k-group
这个题目是上一个的2 --> k的拓展， 对于这个题目采取的做法是在2上进行修改， 其实整体上指针的操作逻辑是没有改变的，1. 指针操作还是需要小心，可以避免区别奇数和偶数的情况，可以统一处理。 2. tail 在
这个题目还是有很多细节要注意，一遍不容易写对。
26. remove duplicates in sorted array
27. remove element
这两个题目都是属于array的操作，也可以应该在string 的操作上，
28. implement strStr()
No comments:
Post a Comment