C++ Summary Reverse Related Problem Set


  • 0
    F

    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;
        }
    };
    

    Reverse Linked List

    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;
        }
    }; 
    

    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) {
            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();
        }
    };
    

    *Reverse Words In a String*

    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 = "";
        }
    };
    
    

    *Reverse Words in a String 2*

    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);
        }
    }
    

Log in to reply
 

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