On Wed, Aug 12, 2009 at 10:38, varun bhatia <[email protected]>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 --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
