Interview Question
bool isRev(node* orig, node*& rev) {
if (!orig && !rev) return true;
if (orig && rev) {
bool match = isRev(orig->next, rev) && (orig->value == rev->value);
rev = rev->next;
return match;
}
return !orig && rev;
}
I think node rev always points to the same element (head)and it doesn't move in the call stack
Ignore previous code, it have a typo
The correct one is
node * check_rev(node *ptr1, node * ptr2)
{
node * reverse_ptr = 0;
if(ptr1->next != 0)
reverse_ptr = check_rev(ptr1->next);
else
reverse_ptr = ptr2;
if(reverse_ptr == 0
|| (*ptr1 != *reverse_ptr))
return 0;
return reverse_ptr->next;
}
@mg
Nice code.
But it fails/seg fault when the length of the lists are unequal ( size of orig > rev) due to the pass by reference argument -- node*& rev.
You'll need to add guard statements to make sure rev is non-null before derefencing rev.
@Ashutosh -- not sure how your code works. check_rev() takes two arguments.
To Be clear:
How can we have a linked list(LIST) and a reversed list(REVLIST) of itself (with physically same nodes). This is not possible.
If we are talking about reversal with respect to data in the list then it is possible.
Algo for this case:
step1: reverse any of the lists
step2: compare data at each node of the both the lists
step3: If corresponding data in the both the lists is same then ANS: Yes
else ANS: "NO"
multiply the data in the first node by 10,second node by 100 and so on...add all the values...multiply the other linked list in decreasing powers of ten...add the values...if both are same then the second one is the reverse of the first
for example consider
1)1->2->3
2)3->2->1
now consider the first list
1*10+2*100+3*1000
we get the result as 3210
now consider the second list
3*1000+2*100+1*10
we get the result as 3210
hence the result
1. Reverse one of the link list and then check for the node to node equality.
- Lord Darth Plagueis August 08, 20092. If the list is doubly linked list - then it is simple.
3. Use recursion to traverse one list => so the u r effectively pushing the list nodes as onto a stack. Now start comparing. If one fails - u terminate. In case one list exhausted and other is still non empty - u terminate. Else u succeed.