smallville
BAN USER/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author nkbansal
*/
public class SubstractReverse {
static class ListNode{
ListNode next;
int data;
public ListNode(int data, ListNode next){
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
int[] input = {5, 4, 3, 2, 1};
ListNode next = null;
for(int i=input.length-1; i>=0;i--){
next = new ListNode(input[i], next);
}
printList(next);
System.out.println("Substract Reverse:");
substractReverse(next,next);
printList(next);
}
public static ListNode substractReverse(ListNode first, ListNode second){
ListNode toSubstract=null;
if (second.next != null){
if(second.next.next != null){
toSubstract = substractReverse(first.next, second.next.next);
}
else{
//E
toSubstract = first.next;
}
}
else{
//Even case
toSubstract = first;
}
first.data-=toSubstract.data;
return toSubstract.next;
}
public static void printList(ListNode node){
while(node!=null){
System.out.print(node.data+"->");
node = node.next;
}
System.out.println(""+null);
}
}
1. Use recursion with two pointer to get the center node.
2. Start backtracking from the center node by returning next pointer to each call.
3. Substract the value of next pointer from the current nodes values
Method hasPool() doesn't call any other method or gets called.
- smallville March 01, 2014if (dp[i-*itr] == 1) {
db[i]=1;
break;
}
It will not work for number=53, which has a possible breakup 9*3+6*4=53
- smallville March 01, 2014The two nodes swapped may not be adjacent to each other in inorder traversal. Instead when you find a node that is out of order do a binary search for the correct position of the node and swap with that node.
- smallville August 30, 2012
This is a implementation:
- smallville May 12, 2014