hack
BAN USERRecursive approach: space O(1) ; time O(n) approx
//Class level variables
int totalLength;
int reversePtr;
int forwardPtr;
int innerFwdPtr;
int innerRevPtr;
Node fwdNode;
boolean isPal = true;
private void recurseNode(Node n) {
if (n==null) {
return;
}
//assumption node does not have empty string
totalLength=totalLength+n.value.length();
recurseNode(n.next) ;
if (!isPal) {
return;
}
for(int i=n.value.length()-1;i>=0;i--,innerFwdPtr++,forwardPtr++) {
if(forwardPtr>=totalLength/2) {
break;
}
char ch = n.value.charAt(i);
if (innerFwdPtr>=fwdNode.value.length()) {
fwdNode=fwdNode.next;
innerFwdPtr=0;
}
//check each char at a time last char vs first char so on ..
if (ch==fwdNode.value.charAt(innerFwdPtr)) {
}else {
isPal=false;
return;
}
}
return;
}
you can do it in 2nlogn+2n (assuming each array has n elements) => sorting each array takes 2 nlog n. iterate through the array takes 2n (like you would do when you merge two sorted arrays)
- hack November 10, 2012