single linked list interview question

Question

say we have a string: MALAYALAM, and each char is data part of each node, so we will have a list of size 9. How do we know whether the list is palindrome or not.

constraints:

• we donot know list length.
• donot use temporary memory(array or stack or another list) for whole list or half of list. usage of few temp chars is acceptable.
• list modification is okay, as long as we have original list by end of operation.

I've few solutions in mind, thought of discussing with everyone. And it is single linked list.

Thanks & Rgds, ~calvin

Answer 1

palindrome = true; //assume initially that it is a palindrome
count = 1;
q = p; // use a temporary pointer for traversing to end
while (q->next) { q = q->next; count ++; } //count the number of elements in the list
do{
   if (p->data != q->data) {palindrome = false; break;}//compare first and last elements of the list under consideration
   p = p->next; count -  = 2; //consider a new linked list with the two end-points cut off
   q = p; for (j = 0; j < count; j++) q = q=>next; 
} while (count > 0);

Answer 2

This one look cool .

Say suppose you have a link-list Node1->Node2->Node3->--->Noden.

let sum1=sum2=0

all you have to do is traverse the list once and compute

           sum1 = (sum1+Nodei->data)*2.

           sum2 += Nodei->data*2^i.

and compare whether they are equal

if equal

   palindrome 

else

   not a palindrome. 

---

Time complexity :O(n)

Space complexity:O(1)

Answer 3

Maybe you could do a divide and conquer solution:

1. go through the list once to establish its length - O(n)
2. go through the list again to position a cursor on the half - you now have cursors A & B - O(n)

3. compare if A is the reverse of B:

   • if length left is greater than some constant, split A into cursors A1 and A2 by traversing, do the same for B1 and B2 - O(n); compare A1 and B2, and A2 and B1 in the same way

   • if length left is smaller than some constant, just brute force compare them - copy B into an array and read it backwards comparing it with A - O(1)

Note that step 3 should be repeated O(logn) times, therefore, the complexity of the solution is O(nlogn).

Complexity analysis in more detail:

f(const) = const

f(n) = f(n/2) + f(n/2) + C*n

Use substitution (n = 2^m, f(2^m) = g(m)) to solve this equation. Solution of this recursion should yield something in the same complexity class as n*logn.

Space complexity is O(logn) because of recursive calls, but that does not seem to be violating any constraints. But the solution could be modified so that it doesn't use recursive calls, but a loop instead - you should only store recursion depth and position at that depth (imagine you have the recursion tree drawn - you simply need 2 integers to store the position in that tree to know what your next step is).

Answer 4

my solution: take fast and slow ptrs, reverse half of the list and compare with another half. And reverse the reversed half so that list will look like original. I'm looking for better solution.

edit: since i couldn't find any better sol.

Answer 5

Based on the requirements they told you here's the solution they want.

1) Find midpoint of list. You can do this by using two pointers and incrementing two nodes and the second by one node. Your second pointer will be at the middle node of the list when the first pointer reaches the end.

2) Reverse the linked list from the middle to the end. You can do this in linear time.

3) Now compare the two lists.

4) Restore the previously reversed list by reversing it again.

Best idea is to write a function to reverse the list in linear time and use it as a helper to the ispalindrome function. This cleans up the code and makes it easier to manage on a whiteboard.

Answer 6

go through the list once to find out its length

then you can check whether character i == character length - i for i=0 to length/2

runs in O(n^2) time and uses O(1) storage

Answer 7

You can do it in O(n) time and O(1) space using randomization.

Step 1: Compute a hash of the string, such as a fingerprint of the whole string.

Step 2: Reverse the linked list.

Step 3: Compute a hash of the reversed string.

Step 4: Reverse the linked list to its original order.

Reversing a linked list can be done in O(n) time and O(1) space as follows:

rev(head) {
  prev = nil;
  curr = head;
  next = head.next;
  while (curr != nil) {
    curr.next = prev;
    prev = curr;
    curr = next;
    next = curr.next;
  }
}

Answer 8

The following should do it in O(n)

1. Recurse to the end of the list, preserve the head pointer.
2. While coming out of the recursive loop, compare the current with the head and move the head to head.next until u run out of characters or find a mismatch.

You can improve this solution by keeping a count of length of the list and stop comparisons after you have reached half the list.

This won't work if the number of characters in the string is greater than the maximum allowed stack depth. In this case, changing the list will work as follows...

Find out the length of the list.

• Keep reversing the links in the linked list as you go until you reach the middle.... once u reach the middle,
• You will have half the list pointing towards the start, the rest will be pointing towards the end.
• Run a while loop till the end and compare corresponding characters and reversing the links again...

Answer 9

This is a brute-force algorithm, hope you get the idea.

<pseudocode>

begin = list.begin();
end = list.end();

while (begin < end) {
   previous = iterator_that_points_to(list, end);
   if (*begin != *previous)
      return false;

   begin++;
   end = previous;
}
return true;

</pseudocode>

While the code for iterator_that_points_to (bear with me for the poor naming) is:

Node* iterator_that_points_to(CharList const& theList, Node* to_find)
{
   Node* iterator = theList.rootNode;
   while (iterator.next != 0) {
      if (iterator.next == to_find)
         return iterator;

      iterator = iterator->next; 
   }
   return 0; // should never happen
}