Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. Update (2014-11-10): Test cases had been added to test the overflow behavior.
First Solution:
First I thought of converting int to string then use two pointer to reverse the number, but we need to pay attention to the two sepcial cases mentioned above. I will update that solution after I solved ‘reverse string’ problem. The following solution uses only one parameter x, we get each digit by computing x%10 and add it to result, then we multiply result with 10 each round. This method deal with first special case of last digit 0 itself, but didn’t pass OJ because of overflows.
1
2
3
4
5
6
7
8
publicintreverse(int x) {
int res=0;
while(x!=0){
res=x%10+res*10;
x=x/10;
}
return res;
}
Correct Solution:
After running a few tests, I figured the overflow probelm occurs when we try to add to Integer.MAX_VALUE(2^32-1), or subtract from Integer.MIN_VALUE(-2^32), this would cause number jump from minus to positive and therefore wrong output. So first we record the sign of the number, and use ABS(x) to compute the ABS of reversed int, during which we check if the new res>Integer.MAX_VALUE,moving res to one side is a really clever trick. At last, output the right sign of result.
1
2
3
4
5
6
7
8
9
10
11
publicintreverse(int x) {
int res=0,num=Math.abs(x);
boolean sign=x>0? true:false;
while(num!=0){
//check if res>Integer.MAX_VALUE
if(res>(Integer.MAX_VALUE-num%10)/10) return0;
res=num%10+res*10;
num=num/10;
}
return sign? res:-res;
}
Reverse Linked List II
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. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
Reverse a Singly LinkedList
First I thought of solving this problem: reverse 1->2->3 to 3->2->1.
Naive solution is to use a stack and reconstruct the list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
publicstatic ListNode reverse(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
while (head != null) {
stack.add(head);
head = head.next;
}
ListNode current = stack.pop();
head = current;
while (!stack.empty()) {
ListNode next = stack.pop();
current.next=next;
current = next;
}
return head;
}
Better solution:
We need to update each node.next
Before that, we need to record the original node.next to continue
Use two pointers, pre to the previous element, and post to the next element
1
2
3
4
5
6
7
8
9
10
public ListNode reverse(ListNode head){
ListNode pre=null,post=null,cur=head;
while(cur!=null){
post=cur.next;
cur.next=pre;
pre=cur;
cur=post;
}
return pre;
}
Iterative Method are even more efficent, but harder to understand…
1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverse(ListNode head){
ListNode cur=head;
if(cur==null||cur.next==null)
return cur;
ListNode post=cur.next;
cur.next=null;
//rest is the last element, the new head
ListNode rest=reverse(post);
//update node.next
post.next=cur;
return rest;
}
Correct Solution:
Different from reverse a Singly LinkedList, we now only need to reverse a part of it (m to n). We use the following pointers:
preM: the last node before m
pre: the last node among the part already reversed. Dont’t need to be udpated, as it always points to the same node
cur: the node we want to add after PreM, in other words, the first node among the part already reversed. Need to be set to pre.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode reverseBetween(ListNode head, int m, int n){
ListNode pre=null,post=null;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode preM=dummy,cur=null;
for (int i =1;i<=n;i++){
if(i<m)
preM=preM.next;
elseif(i==m){
pre=preM.next;
cur=pre.next;
}
else{
pre.next=cur.next;
//made a mistake here by cur.next=pre;
cur.next=preM.next;
preM.next=cur;
cur=pre.next;
}
}
return dummy.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. Only constant memory is allowed. For example, Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5
Iterative Solution:
We use the sub-process of reverse(ListNode start,ListNode end), while we scan through the list, keep three pointers:
pref: breakpoint for different groups.
start: first node of current group. Initialized as node 1
end: last node of current group
Each round we:
move pref to position, set start and end pointer
reverse current group, link last node to the rest
link pref to the returned head, and repeat
This is One Pass O(n) solution.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode pref=dummy, start, end;
while(pref!=null){
start=pref.next;
end=pref;
//move end pointer K times, pointing to kth node
for (int i=0;i<k;i++){
end=end.next;
//last nodes not enough for a group
if(end==null) return dummy.next;
}
//link pref with head of reversed group
pref.next=reverse(start,end);
//move pref pointer K times, pointing to the node before next group
for(int j=0;j<k;j++){pref=pref.next;}
} return dummy.next;
}
public ListNode reverse(ListNode start,ListNode end){
ListNode post=end.next,tmp;
ListNode pre=start,cur=start.next;
//inside this group
while(cur!=post){
tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
//don't forget to link end of reversed group with the rest nodes
start.next=post;
return pre;
}
Two Pass Solution:
I first thought of this solution, but wasn’t careful enough with the details…
First scan through the list and get the number of groups
For each group i smaller than num, use an inner loop to do the following:
reverse each group, keep curhead and curtail as inner group pointers, move cur to first node outside of group
if is the first group, we update head and let tail=curtail, in other rounds we just attach curhead to tail.
At last, don’t forget to attach the leftover nodes curtail.next=cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public ListNode reverseKGroup(ListNode head,int k){
Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
Naive Solution
First count the length of list, link the last node with head to form a loop. Now cur is pointing to the last node, we use a for loop to move it to (n-k)th node, and break the loop there. At last, return (n-k).next as new head.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode rotateRight(ListNode head, int n) {
int k=1;
ListNode cur=head;
if(cur==null||cur.next==null||n==0) return head;
while(cur.next!=null){cur=cur.next;k++;}
cur.next=head;
//set n to the position of new head in the original list
