Check if the linked list is palindromic

Question

Consider a linked list whose nodes are characters, so the list represents a string. How do you write a recursive routine to check if a string is a palindrome such that this function begins to unwind the stack when it processes the character (s) in the middle of the string?

For example, suppose my line is "Madame." My recursive function looks something like this:

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

When currentnode->data == 'd' , the stack should spin up.

I was asked this question for an interview; at the moment I cannot think of any use for this question, except as a very difficult riddle.

First thoughts: a very obvious (if inelegant) way:

• First calculate the midpoint of the list.
• If currentnode is before midpoint , push the former midpoint stack manually. This can be solved by maintaining a counter.
• Otherwise, manually unwind the supported stack at each recursion step and compare with the current character.

Any better ideas or fresh ideas?

Answer 1

If you really enjoy using the stack, this is a common exercise in computational theory using non-deterministic automata. The idea is to push each char onto the stack and on each char, disconnect, with one branch skipping char (in case it is an odd palindrome) and pushing each char from the stack when comparing to one in the rest of the list, the other branch does the same thing, not skipping this initial char (in case it is the only palindrome), and the third continues to add elements to the stack (and starts branching recursively with the next char). These three branches can be represented by passing the current state of the stack to each recursively.

In pseudo code:

 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 2

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 used the fact that it is possible to iterate from the end as well as forward from the very beginning. It is unclear whether this is being asked.

With a singly linked list, you can run two iterators, one fast and one slow. For each call, increase speed once and slow once. When fast reaches the end of the list, slow is at the midpoint (um, +/- 1 and takes into account lists of odd length and even length). At this point, return from your recursion by comparing character values. & Theta; (n) complexity for use during operation and memory (not recursive).

I would write the code, but it's time to sleep 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 does not provide an iterator, then hopefully the equivalent code with if (fast->next == 0) , fast = fast->next , etc. obvious. And of course, you can remove the user interface with a wrapper.

I think you can avoid additional storage if you are allowed to temporarily change the list by flipping the list to "slow" when you go down, and then turn it over again when you go up. Thus, you do not need to store a copy of slow on a recursive call: instead, you can return an extra pointer for a subsequent call. However, I will not worry.

]

Answer 3

Modulo thorny details this simple.

First find the midpoint by calling recursively moving one pointer just one step, but the other two steps. When the two-step pointer reaches the end, the one-step pointer is in the middle. The subtle thing: even against a list of odd lengths.

Then back up (return from recursive calls), and with support, click one step forward for each return. Just compare the contents of the node with the contents available as a normal argument during descent.

Cheers and hth.,

Answer 4

Is the list linked twice? Then it's a matter of going through the start and end nodes, compare what they point to. If they are different, return false. If they match, call yourself recursively with start + 1 and end-1 until you start> end.

Answer 5

that's what i asked

 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

In Java, this solution will compare a string already read with a string that comes in recursively. This is not the best solution, since even if O (n) is S (n ^ 2), and he should (at least) use StringBuffer to reduce all concatenations.

It uses a wrapper class to return the right side of the string along with the boolean.

pros:

• only one pass to the list, from head to end.
• he does not need to know the length of the list in advance
• No additional data structures required

minuses:

• uses memory load S (n ^ 2)
• concatenate rows in an inefficient way
• 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 7

• Find the length of a common string
• Get a node that has a middle (middle) position
• Break the list into node
• Flip the first half

• Now compare the line

  include "stdafx.h"

  enable "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 8

To start, go to the end of the list and save the pointer to the last node as end . Then save the pointer to the first node as start .

Then call the function and supply these values. The function will be:

• Check if start == end (they point to the same link). If so, he will return immediately. (An odd number of items in the list, and the middle item is only one.)
• He will then look at the values ​​represented by start and end . If they are not equal, it will immediately return false. (Not a palindrome).
• Otherwise, it will change start to point to the next link (presumably start = start->next ).
• If start == end , immediately return true (handles the case for an even number of links in the list).
• Find the link to end and set end to it: link i = start; while (i->next != end) i = i->next; end = i; link i = start; while (i->next != end) i = i->next; end = i; .
• Record the new values ​​for start and end .

Answer 9

Below is the recursion code where node has data as integer, just replace it with char. It works in O (n) time, uses constant space, different from the implicit use of a stack of size O (n). where n is the number of nodes in the list of links.

 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 10

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

1) Calculate the length LL,
2) Find a suitable middle
// (for length 5, the midpoint is 3, but for length 4, the midpoint is 2).
3) When at the midpoint - cancel LL from midpoint to end LL;
4) Compare the head data with the new average until the head repeats to the middle and the new average ref repeats to NULL.