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* reverseList(ListNode* head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = head;
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:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *p = head;
head = reverseList(p->next);
//p->next now is the tail node, so we set the p->next->next = p
p->next->next = p;
p->next = NULL;
return head;
}
};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) {
ListNode* new_head = new ListNode(0);
new_head -> next = head;
ListNode* pre = new_head;
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;
}
return new_head -> next;
}
}; 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) {
ListNode *cur = head;
for (int i = 0; i < k; ++i) {
if (!cur) return head;
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 *new_head = reverse(head, cur);
head->next = reverseKGroup(cur, k);
return new_head;
}
ListNode* reverse(ListNode* head, ListNode* tail) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode *cur = head;
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);
}
}