Checking if Linked List is palindromic

Question

Consider a linked list whose nodes are chars, so the list represents a string. How do you write a recursive routine to check whether the string is a palindrome such that the the said function starts unwinding the stack when it processes the character(s) at the middle of the string?

For example, suppose that my string is "madam". My recursive function looks something like:

bool isPalin(const node *startnode, const node *currentnode, const node *midpoint, ...);

When currentnode->data == 'd', the stack has to unwind.

I was asked this question for an interview; at the moment I can't think of any use for this question except as a very hard puzzle.

First thoughts: A very obvious (if inelegant) way is to:

1. Compute the midpoint of the list first.
2. If currentnode is "before" midpoint , push former into a stack manually. This can be decided by maintaining a counter.
3. Otherwise, unwind the manually maintained stack at every step of the recursion, and compare with the current character.

Any better ideas or fresh insights?

Answer 1

1. Find the length of the total string
2. Get the node that has the mid (middle) position
3. Break the List at that node
4. Reverse the first half

5. Now do string compare

   include "stdafx.h"

   include "LinkedList.h"

LinkedList::LinkedList() { head = nullptr; count = 0; }

void LinkedList::AddItem(char* data) { Node node = new Node; node->Data = (void) malloc(strlen(data) + 1);

strcpy((char*)node->Data, data);
node->Data = data;
node->Next = nullptr;
count++;

if(head == nullptr)
{
    head = node;        
    head->Next = nullptr;
    return;
}

Node *temp = head;

while(temp->Next!=nullptr)
{
    temp = temp->Next;
}

temp->Next = node;

}

void LinkedList::TraverseList() { Node *temp = head;

while(temp !=nullptr)
{
    printf("%s \n", temp->Data);
    temp = temp->Next;
}

}

Node* LinkedList::Reverse() { if(!head || !(head->Next)) { return head; }

Node* temp = head;

Node* tempN = head->Next;

Node* prev = nullptr;

while(tempN)
{
    temp->Next = prev;

    prev= temp;
    temp = tempN;

    tempN = temp->Next;
}

temp->Next = prev;
head = temp;
return temp;

}

bool LinkedList::IsPalindrome() { int len = 0; Node* temp = head;

while(temp)
{
    len = len + strlen((char*)temp->Data);
    temp = temp->Next;
}

printf("total string length is %d \n", len);

int i =0;
int mid1 = 0;

temp = head;

while (i < len/2)
{
    int templen = strlen((char*)temp->Data);        

    if(i + strlen((char*)temp->Data) < (len /2))
    {
        i = i + strlen((char*)temp->Data);
        temp = temp->Next;
    }
    else
    {
        while(i < len/2)
        {
            mid1++;
            i++;
        }

        break;
    }
}

printf("len:%d, i:%d, mid1:%d mid2:%d \n",len, i, mid1, len-mid1);

Node* secondHalf = temp->Next;
temp->Next = nullptr;
Node *firstHalf = Reverse();

char* str1 = (char*)malloc(sizeof(char) * mid1 + 1);
char* str2 = (char*)malloc(sizeof(char) * mid1 + 1);

memcpy(str1, (char*)firstHalf->Data, mid1); 
str1[mid1] = '\0';

int slen = strlen((char*)temp->Data);

if(slen > mid1)
{
    memcpy(str2, (char*)firstHalf->Data + mid1, slen-mid1);
    str2[slen-mid1] = '\0';
}
else
{
    str2[0] = '\0';
}   

printf("%s, %s", str1, str2);
str1 = strrev(str1);

if(!*str2)
{
    str2 = (char*)secondHalf->Data;
    secondHalf = secondHalf->Next;
}

if(*str2 && len%2 == 1)
{
    str2++;
    if(!*str2)
    {
        str2 = (char*)secondHalf->Data;
        secondHalf = secondHalf->Next;
    }
}

while(*str1 && *str2)
{
    if(*str1 != *str2)
    {
        return false;
    }

    str1++;
    str2++;

    if(!*str1)
    {   
        retry:
        firstHalf = firstHalf->Next;
        if(firstHalf)
        {
            str1 = (char*) malloc(strlen((char*)firstHalf->Data) + 1);
            strcpy(str1,(char*)firstHalf->Data);                
            str1 = strrev(str1);
        }

        if(!*str1 && firstHalf)
        {
            goto retry;
        }
    }

    if(!*str2)
    {
        retrySecondHalf:
        temp = secondHalf;
        if(temp)
        {
            str2 = (char*)temp->Data;           
            secondHalf = secondHalf->Next;
        }

        if(!*str2 && secondHalf)
        {
            goto retrySecondHalf;
        }
    }
}

if(*str1 || *str2)
{
    return false;
}

return true;

}

int _tmain(int argc, _TCHAR* argv[]) { LinkedList* list = new LinkedList();

list->AddItem("01234");
list->AddItem("");
list->AddItem("56");
list->AddItem("789");
list->AddItem("1"); 
list->AddItem("9");
list->AddItem("");
list->AddItem("876543210");

printf("Is pallindrome: %d \n", list->IsPalindrome());

return 0;

}

Answer 2

In Java, this solution will compare the string already read against the string that comes recursively. It's not the best solution as even when it's O(n) it's S(n^2) and it should (at least) use StringBuffer to reduce all the concatenations.

It makes use of a wrapper class to pass back the right side of the string along with the boolean.

pros:

1. only one pass to the list, from head to end.
2. it doesn't need to know in advance the list length
3. no extra data structures needed

cons:

1. uses loads of memory S(n^2)
2. concatenates strings in an inefficient way
3. recursive solution, slow.

Code:

boolean palindrome(Node n){
    RightSide v = palindromeRec(“”, n);
    return v.palindrome;
}

class RightSide{
    boolean palindrome;
    String right;
}

private RightSide palindromeRec(String read, Node n){
    RightSide v = new RightSide();

    if(n == null){
        v.palindrome = false;
        v.right = “”;
        return v;
    }

    v = palindromeRec(n.value + read, n.next);

    if(v.palindrome) 
        return v;
    else if(read.equals(v.right) || (n.value+read).equals(v.right)){
        v.palindrome = true;
        return v;
    }

    v.right = n.value + v.right;
    v.palindrome = false;

    return v;
}

Answer 3

Following is recursion code, where node has data as integer, just replace it with char. It runns in O(n) time, uses constant space other than implicitly using stack of size O(n). where, n is number of nodes in linkedlist..

package linkedList;
class LinkedList {
    class LinkedListNode {
        public int data;
        public LinkedListNode next;
        public LinkedListNode (int d) {
            data = d;
            next = null;
        }
    }

    class PalinResult {
        public boolean done;
        public LinkedListNode forward;

        public PalinResult (LinkedListNode n) {
            forward = n;
            done = false;
        }
    }

    LinkedListNode root;

    public LinkedList () {
        root = null;
    }

    public LinkedListNode getRoot(){
        return root;
    }

    public boolean add(int d) {
        LinkedListNode t = new LinkedListNode (d);
        if (root == null) {
            root = t;
            return true;
        }

        LinkedListNode curr = root;
        while (curr.next != null) {
            curr = curr.next;
        }

        curr.next = t;
        return true;
    }

    /*
     * Takes O(n time)
     */
    public boolean checkPalindrome() {
        PalinResult res = new PalinResult (root);
        return     checkPalindromeRecur(root, res);
    }

    private boolean checkPalindromeRecur(LinkedListNode curr, PalinResult res) {
        if (curr == null) 
            return true;
        else {
            boolean ret = checkPalindromeRecur(curr.next, res);

            if (!ret || (res.done))
                return ret;

            if (curr == res.forward)
                res.done = true;

            if (curr.data == res.forward.data)
                ret = true;
            else
                ret = false;

            res.forward = res.forward.next;
            return ret;
        }
    }

    public static void main(String args[]){
        LinkedList l = new LinkedList();
        l.add(1);
        l.add(4);
        l.add(1);

        System.out.println(l.checkPalindrome());
    }
}

Answer 4

So ( My rough idea- please let me know) We could also

1) Calculate length of LL;
2) Appropriately determine the midpoint
// (for a length 5 the mid point is 3 but for length 4 the midpoint is 2).
3) When at Midpoint- reverse the LL from mid point to the end of the LL;
4)Compare head data with the new mid point data until the head ref iterates to mid and the new mid ref iterates to NULL.

Answer 5

this is what the asked I think

bool isPalindrom(node* head)
{
   if(!head) return true;

   node* left = head;
   node* mid = head;

   return cmp(left, mid, head);
}

bool cmp(node*& left, node*& mid, node* n)
{
   node* next = n->next;   

   if(next == 0)
   {
      node* lprev = left;
      left = left->next;
      return lprev->data == n->data;      
   }

   mid = mid->next;
   if(next->next == 0)
   {
      node* lprev = left;
      left = left->next->next;
      return lprev->data == next->data && lprev->next->data == n->data;
   }

   if(!cmp(left, mid, next->next)) return false;

   if(left == mid) return true;

   if(left->data != next->data) return false;

   left = left->next;

   if(left == mid) return true;

   if(left->data != n->data) return false;

   left = left->next;

   return true;
}

Answer 6

By "linked list", do you mean std::list?

template <typename BiDiIterator>
bool isPalindrome(BiDiIterator first, BiDiIterator last) {
    if (first == last) return true;
    --last;
    if (first == last) return true;
    if (*first != *last) return false;
    return isPalindrome(++first, last); // tail recursion FTW
}

isPalindrome(mylist.begin(), mylist.end());

I've used the fact that it's possible to iterate back from the end as well as forward from the start. It is not clear whether this is given by the question.

With a singly linked list you can run two iterators, one fast and one slow. On each call, increment the fast one twice and the slow one once. When the fast one reaches the end of the list, the slow one is at the midpoint (um, +/- 1 and taking account of odd-length and even-length lists). At that point, back out of your recursion comparing character values. Θ(n) complexity for runtime and memory use (not tail recursive).

I'd write the code, but it's time for bed here in the UK.

[Edit: morning all

template <typename FwdIterator>
std::pair<FwdIterator, bool> isPalindrome(FwdIterator slow, FwdIterator fast, FwdIterator last) {
    if (fast == last) return std::make_pair(slow, true);
    ++fast;
    if (fast == last) return std::make_pair(++slow, true);
    ++fast;
    FwdIterator next = slow;
    std::pair<FwdIterator, bool> result = isPalindrome(++next, fast, last);
    if (result.second == false) return result;
    if (*slow != *(result.first)) return std::make_pair(slow, false);
    ++(result.first);
    return result;
}

...

isPalindrome(mylist.begin(), mylist.begin(), mylist.end()).second;

If, for some bizarre reason, your linked list doesn't provide an iterator, then hopefully the equivalent code with if (fast->next == 0), fast = fast->next, etc, is obvious. And of course you can tidy up the user interface with a wrapper.

I think you can avoid the additional storage if you're allowed to temporarily modify the list, by reversing the list up to "slow" as you descend, then reversing it again as you ascend. That way you don't need to store a copy of slow across the recursive call: instead you can return an extra pointer for the caller to follow. I'm not going to bother, though.

]

Answer 7

If you do feel like using a stack, this is a common exercise in computation theory using nondeterministic pushdown automata. The idea is to push every char onto the stack and at each char, branch off, with one branch skipping a char (in case it's an odd palindrome) and popping each char off the stack while comparing it to one in the remainder of the list, another branch doing the same without skipping that initial char (in case it's an even palindrome), and the third continuing to add elements to the stack (and recursively beginning the branching again with the next char). These three branches could be represented by passing the current state of the stack into each one recursively.

In pseudocode:

function isPalin(* start, * end, stack){
  if checkPalin(start, end, stack):
    return true;

  stack.push(*start);
  if checkPalin(start, end, stack):
    return true;

  if (start == end)
    return false;

  return isPalin(start.next, end, stack);
}

function checkPalin(* start, * end, stack){
  while (stack is not empty && start != end){
    start = start.next;
    if (*start != stack.pop())
      return false;
  }

  return (stack is empty && start == end);
}

Answer 8

Modulo thorny details this one's easy.

First, find the midpoint by calling recursively moving one pointer just one step but other two steps. When two-step pointer reaches end one-step pointer is at middle. Thorny thing: even versus odd length list.

Then back up (returning from the recursive calls), and while backing move midpointer one step forward for each return. Just compare that node's contents with contents available as routine argument during descent.

Cheers & hth.,

Answer 9

Is the list doubly linked? Then it's a matter of passing in the start and end nodes, compare what they point to. If they're different, return false. If they're the same, call yourself recursively with start+1 and end-1, until start > end.

Answer 10

To begin, iterate to the end of the list and store a pointer to the last node as end. Then store a pointer to the first node as start.

Then, call a function and supply these values. The function will:

1. Test if start == end (they point to the same link). If so, it will return true immediately. (An odd number of items in the list and the middle item is the only one left.)
2. Then it will look at the values represented by start and end. If they are not equal, it will return false immediately. (Not a palindrome.)
3. Otherwise, it will alter start to point to the next link (presumably start = start->next).
4. If start == end, return true immediately (handles the case for an even number of links in the list).
5. Find the link prior to end and set end to it: link i = start; while (i->next != end) i = i->next; end = i;.
6. Recurse, supplying the new values for start and end.