Approach #1 use signed int [Accepted]
class Solution
{
public:
int reverse(int x)
{
int sign, output;
(x > 0) ? (sign = 1) : (sign = 0, x = x);
for (output = 0; x > 0; x /= 10)
{
if (output > 0x7fffffff / 10)
return 0;
output = output * 10 + x % 10;
}
return sign ? output : output;
}
};
Time complexity: O(n)
Space complexity: O(1)
We are going to move the lowest digit of input **x** to the **output** as its new lowest digit, then repeat the action until the numbers of **x** run out. As for the sign of **x**, here is an addition step to mark the sign and transform **x** to its opposite before the iteration.
Do not compare a **int** with marcro **INT_MAX** or **INT_MIN** directly because once a variable (**temp** for example) saves as **int**, it always satisfies **INT_MIN** <= **temp** && **temp** <= ***INT_MAX** and it is impossible to catch overflow by the comparsion.
Since the problem require a 32bit integer input, we illustrate here with 2147483647 = 2^{31}  1 instead of **INT_MAX**.

If we get a intermediate result not larger than 214748363, it is OK whatever the lowest digit of x remianed is, because the operatation
output = output * 10 + x % 10;
produce a value not more than 2147483639, which is proper for a int. 
If we get a intermediate result as 214748364, meanwhile the lowest digit of x remianed is 0 or 1 or 2 or ... or 7, it is still OK because the operatation
output = output * 10 + x % 10;
produce a value not more than 2147483647. Although it seems to fail if the lowest digit of x remianed is 8 or 9, but it is impossible to happen for the input x itself satisfies x <= INT_MAX and the largest value possible is 2147483641 <=> 1463847412. So the conditionif (output > 0x7fffffff / 10)
is enough.
Approach #2 use long long [Accepted]
class Solution
{
public:
int reverse(int x)
{
int sign;
long long output;
(x > 0) ? (sign = 1) : (sign = 0, x = x);
for (output = 0; x > 0; x /= 10)
{
output = output * 10 + x % 10;
if (output > 0x7fffffff)
return 0;
}
return sign ? output : (signed int)output;
}
};
Time complexity: O(n)
Space complexity: O(1)
Another way to catch overflow is using a longer datatype such as **long long** and compare it with **INT_MAX**, the idea is easy to come up with but maybe slower then the signed int approach.