C++ Summary Reverse Related Problem Set

• Reverse Interger : Reverse digits of an integer.

Frist, we can check the direct solution :

``````class Solution {
public:
int reverse(int x) {
long long res = 0;
while(x) {
res = res*10 + x%10;
x /= 10;
}
return (res<INT_MIN || res>INT_MAX) ? 0 : res;
}
};
``````

Here is a better solution :

``````class Solution {
public:
int reverse(int x) {
int res = 0;
while (x != 0) {
if (abs(res) > INT_MAX / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
``````

Here is a iterative solution by me

``````class Solution {
public:
ListNode *dummy = new ListNode(-1);
while (cur->next) {
ListNode *move = cur->next;
cur->next = move->next;
move->next = dummy->next;
dummy->next = move;
}
return dummy->next;
}
};
``````

Let us check the Recursive solution , it is a little bit hard to understand at first ,

``````class Solution {
public:
//p->next now is the tail node, so we set the p->next->next = p
p->next->next = p;
p->next = NULL;
}
};
``````

Revserse Linked List 2 Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

``````class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
for (int i = 0; i < m - 1; i++)
pre = pre -> next;

ListNode* cur = pre -> next;
for (int i = 0; i < n - m; i++) {
ListNode* move = cur -> next;
cur -> next = move -> next;
move -> next = pre -> next;
pre -> next = move;
}
}
};
``````

Reverse Nodes in K-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed.

``````class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
for (int i = 0; i < k; ++i) {
cur = cur->next;
}
//current is the k-nodes-groud's next node
//so we reverse the from head to the previous node of cur
}
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* dummy = new ListNode(0);

while (cur->next != tail) {
ListNode* move = cur->next;
cur -> next = move -> next;
move -> next = dummy -> next;
dummy -> next = move;
}
return dummy->next;
}
};
``````

Evaluate Reverse Polish Notation*

``````class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stn;
for (auto it : tokens) {
if (it.size() > 1 || isdigit(it[0])) {
stn.push(stoi(it));
}
else {
int op2 = stn.top(); stn.pop();
int op1 = stn.top(); stn.pop();
switch(it[0]) {
case '+' : stn.push(op1 + op2); break;
case '-' : stn.push(op1 - op2); break;
case '*' : stn.push(op1 * op2); break;
case '/' : stn.push(op1 / op2); break;
}
}
}
return stn.top();
}
};
``````

Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the".

In fact, this problem is far harder than my imagination !!! We need to check it clearly !!!

``````class Solution {
public:
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int storeIndex = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
if (storeIndex != 0) s[storeIndex++] = ' ';
int j = i;
while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
i = j;
}
}
s.erase(s.begin() + storeIndex, s.end());
}
};

``````

Here is more easy to understand solution :

``````
class Solution {
public:
void reverseWords(string &s) {
int i = 0, j = 0;
int l = 0;
int len = s.size();
int word_count = 0;
while (true) {
// skip spaces in front of the word
while (i < len && s[i] == ' ') i++;
if (i == len) break;
if (word_count) s[j++] = ' ';
l = j;
while (i < len && s[i] != ' ') { s[j++] = s[i++]; }
reverse_word(s, l, j - 1);
word_count++;
}
s.resize(j);
reverse_word(s, 0, j - 1);
}

void reverse_word(string &s, int i, int j) {
while (i < j) {
char t = s[i];
s[i] = s[j];
s[j] = t;
i++, j--;
}
}
};
``````

Let us check a better solution :

``````class Solution {
public:
void reverseWords(string &s) {
istringstream is(s);
string tmp;
is >> s;
while (is >> tmp) s = tmp + " " + s;
if (s[0] == ' ') s = "";
}
};

``````
``````void reverseWords(string &s) {
reverse(s.begin(), s.end());
for (int i = 0, j = 0; i < s.size(); i = j + 1) {
for (j = i; j < s.size() && !isblank(s[j]); ++j);
reverse(s.begin()+i, s.begin()+j);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.