well the 2nd ques is not clear............................. can u explain it in simpler manner
On Wed, Aug 12, 2009 at 4:37 PM, Aravind Narayanan <a.cyber...@gmail.com>wrote: > > On Wed, Aug 12, 2009 at 10:38, varun bhatia <varunbhatia....@gmail.com>wrote: > >> 1. Given a single link list with one info part containing single character >> and a link. Check whether the link list is a palindrome or not. >> The algo should run in Linear time only. You can't use any array or string >> to store the string of link-list. > > > a. Find the length of the linked list by traversing it once. > > b. Knowing the length, you can now reverse all of the pointers in the second > half of the linked list > c. Traverse the list from both sides, comparing values as you go towards the > center. > Find if the list is a palindrome. > d. Reset the linked list if needed. > > >> 2. You are given a Double Link List with one pointer of each node pointing >> to the next node just like in a single link list. The second pointer however >> CAN point to any node in the list and not just the previous node. >> Now write a program in O(n) time to duplicate this list. That is, write a >> program which will create a copy of this list. > > > Lets call the first list A, and say that we need to create list B. > > a. Traverse list A, creating the corresponding node for list B as you go. > Set the first pointer of each node in list B to point to the next node. Set > the second pointer of each node in list B to point to the corresponding node > in list A. Set the first pointer of each node in List A to point to the > corresponding node in List B. > b. Now traverse list B. For each node 'x' in list B, follow the second > pointer of that node to get to the corresponding node 'm' in List A. Then > follow the second pointer of the node 'm' in list A to get to the required > node 'n' in list A. Now, from this node 'n' in list A, follow the first > pointer to get to a node 'y' in List B. Set the second pointer of node 'x' > to point to node 'y'. However, before you reset the second pointer of a node > in List B, you need to set the first pointer of node 'm' in list A to point > to the correct next node. This can be done by following the first pointer of > node 'x' to node 'z', and then the second pointer to required node 'm-dash' > in list A. > > Hope that makes sense. > > ~ Aravind > > > > -- Regards, Varun Bhatia MCA Department of Computer Science, University of Delhi, Delhi - 110007 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
