A single linked list is a palindrome or not

Question

I have a Single Linked List. I want to find whether the Linked List is Palindrome or not. I implemented it in one way, as shown below.

bool palindromeOrNot(node *head) { node *tailPointer; node *headLocal=head; node *reverseList=reverseLinkedListIteratively(head); int response=1; while(headLocal != NULL && reverseList!=NULL) { if(headLocal->id==reverseList->id) { headLocal=headLocal->next; reverseList=reverseList->next; } else return false; } if(headLocal == NULL && reverseList==NULL) return fasle; else return true; } 

I change the original Linked List and then compare Node with Node. If everything is in order then I will return 1 else return 0.

Is there a better algorithm to solve the problem.

Answer 1

METHOD 1 (Use the stack)

A simple solution is to use a stack of list nodes. It basically consists of three steps.

• Drag this list from head to tail and click on each visited node stack.
• Move the list again. For each visited node, enter a node from the stack and compare the data of the pop-up node with the current visited node.
• If all nodes are consistent then return true, else false.

The complexity of time is higher than the O (n) method, but this requires O (n) extra space. The following methods solve this with constant extra space.

METHOD 2 (by changing the list)

This method takes O (n) time and O (1) extra space.

• Get the middle of the linked list.
• Flip the second half of the linked list.
• Check if the first and second half are identical.
• Build the original linked list by modifying the second half again and returning it to the first half.

METHOD 3 (Using recursion)

Use the two pointers left and right. Move right and left using recursion, and check the following in each recursive call.

• A sub-list is a palindrome.
• The value in the current left and right matches.

If both conditions are above true, return true.

The idea is to use the function call stack as a container. Move recursively to the end of the list. When we return from the last NULL, we will finally be node. The last node to compare with the first node of the list.

To access the first list of nodes, we need the list of headers to be available in the last recursion call. Therefore, we also pass to the recursive function. If they match, we need to compare the (2, n-2) nodes. Again, when recursion returns to (n-2) nd node, we need a link to the 2nd node from the head. We advance the chapter pointer in the previous call to refer to the next node in the list.

However, the trick in defining a double pointer. Passing a single pointer is as good as bandwidth, and we will pass the same pointer again and again. We need to pass the address of the main pointer to reflect the changes in the parent recursive calls.

Optional: geeksforgeeks

Answer 2

Whether a single-linked list is Palindrome or not , can also be checked without reversing the linked list

You can turn to the recursive approach, which will compare a pointer pointing to the beginning of a linked list and another pointer returning from recursion from the last.

Here is the pseudo code:

 int isPalindrome(**root,*head) { if(!head) return 1; else { int res = isPalindrome(root,head->next); if(res == 0) return 0; int r = (*root)->data == head->data; *root = (*root)->next; return r; } } 

The call is made as follows: isPalindrome(&root,root);

Answer 3

When we compare a linked list with an inverted list, we really may need to compare only the first half of the list. If the first half of the normal list corresponds to the first half, if the list is inverse, then the second half of the normal list should correspond to the second half of the inverted list.

Answer 4

Only reverse half of the linked list. And start comparing. You do not need to reverse entire linked list.

Answer 5

You can also check it with arrays. First, go through the list of links from its root and save the data field of each node into an array, and then cancel this array, and then compare both elements one at a time. Below is the program

  bool isPalindrome(Node *head) { int i=0,j,n=0,arr1[50],arr2[50]; struct Node *current; current=head; while(current!=NULL) { arr1[i]=current->data; i++; n++; current=current->next; } j=0; for(i=n-1;i>=0;i--) { arr2[j]=arr1[i]; j++; } for(i=0;i<n;i++) { if(arr1[i]!=arr2[i]) { return false; } } return true; } 

Answer 6

Why are you making it complicated. Since this is homework. I can just give you a simple suggestion. I notice that you are only comparing id in your code. suppose your id is a char, why don't you just go through the list once and store the char in an array, and then check for a palindrome . your path simply changes the linked list once and twice goes through the linked list completely there are three workarounds.

Answer 7

I think you could get a better solution in terms of using O (1) memory and the same O (n) speed. By working with a linked list in place. You do not need to back up the linked list. However, these methods destroy the list. You will have to stitch it in place, but the runtime will still be O (n).

The code for the quick version of isPalindrome basically finds the middle of the linked list, and then logically breaks the linked list into 2 parts. He changes only the first part into place and compares it with another part. The bad part is the destruction of the linked list due to a spread in the first linked list. However, you can stitch the lists back into place and still be in O (n) time.

View function isPalindromeFast. I started, but still not finished, stick-lists. You can run the code in the Go game here http://play.golang.org/p/3pb4hxdRIp .

Here is the complete code in Go.

 package main import "fmt" type Node struct { value string next *Node } func (n *Node) Next() *Node { return n.next } func (n *Node) Value() string { return n.value } func (n *Node) Length() int { length := 0 linkedList := n for linkedList != nil { length += 1 linkedList = linkedList.Next() } return length } func NewLinkedList(s string) *Node { if len(s) == 0 { return nil } headNode := &Node{string(s[0]), nil} currentNode := headNode for _, v := range s[1:] { newNode := &Node{string(v), nil} currentNode.next = newNode currentNode = newNode } return headNode } func PrintLinkedList(linkedList *Node) { for linkedList != nil { fmt.Println(linkedList) linkedList = linkedList.Next() } } func ReverseList(linkedList *Node, endPoint int) *Node { if endPoint == 1 { return linkedList } first, next, lastNode := linkedList, linkedList, linkedList lastNode = nil for i := 0; i < endPoint; i++ { next = first.Next() first.next = lastNode lastNode = first first = next } return lastNode } // func StitchListsBackTogether(listA, listB, listC *Node, endOfListA int) *Node { // listAFixed := ReverseList(listA, endOfListA) // listStart := listAFixed // for listAFixed.Next() != nil { // listAFixed = listAFixed.Next() // } // listAFixed.next = listB // return listStart // } func IsPalindromeFast(linkedList *Node) bool { // Uses O(1) space and O(n) time // However mutates and destroys list, so need to stitch list backtogether. Initial implementation StitchListsBackTogether length := linkedList.Length() endOfListA := length / 2 endOfListB := length / 2 if length%2 == 0 { endOfListB += 1 } else { endOfListB += 2 } listA, listB := linkedList, linkedList for i := 0; i < endOfListB-1; i++ { listB = listB.Next() } listA = ReverseList(listA, endOfListA) for listA != nil && listB != nil { if listA.Value() != listB.Value() { return false } listA = listA.Next() listB = listB.Next() } return true } func IsPalindromeSlow(linkedList *Node) bool { //Uses O(1) space and O(n^2) time startPalidrome, endPalidrome := linkedList, linkedList for endPalidrome.Next() != nil { endPalidrome = endPalidrome.Next() } for startPalidrome != endPalidrome { if startPalidrome.Value() != endPalidrome.Value() { return false } if startPalidrome.Next() == endPalidrome { return true } startPalidrome = startPalidrome.Next() middlePalidrome := startPalidrome for middlePalidrome.Next() != endPalidrome { middlePalidrome = middlePalidrome.Next() } endPalidrome = middlePalidrome } return true } func main() { fmt.Println(IsPalindromeSlow(NewLinkedList("ttoott"))) fmt.Println(IsPalindromeFast(NewLinkedList("ttoott"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("ttott"))) fmt.Println(IsPalindromeFast(NewLinkedList("ttott"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("hello"))) fmt.Println(IsPalindromeFast(NewLinkedList("hello"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("ttto"))) fmt.Println(IsPalindromeFast(NewLinkedList("ttto"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("tt"))) fmt.Println(IsPalindromeFast(NewLinkedList("tt"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("t"))) fmt.Println(IsPalindromeFast(NewLinkedList("t"))) fmt.Println("") fmt.Println(IsPalindromeSlow(NewLinkedList("tto3tt"))) fmt.Println(IsPalindromeFast(NewLinkedList("tto3tt"))) fmt.Println("") } 

Answer 8

Here is my solution to this problem. To test it, I used integers instead of characters. For example, I used 1,4,1,4,1 instead of "adada". You can change int to char, and everything should work.

 struct Node { Node(int in) : data(in) {} int data; Node* next; }; //This function will find recursively call itself until last element and than it will start //comparing. To compare with correct element from the beginning a paramater called pos is used bool palindromeStart(Node* first, Node* last, size_t pos, size_t middlePos) { if (last->next != NULL) { if (palindromeStart(first, last->next, pos + 1, middlePos) == false) return false; } size_t curPos = middlePos - pos; while (curPos--) first = first->next; if (first->data != last->data) return false; return true; } bool isPalindrome(Node* head) { Node* n1 = head; Node* n2 = head; size_t middlePos = 0; while (true) { if (n2 == nullptr) { --middlePos; break; } else if ( n2->next == nullptr) { break; } n2 = n2->next->next; n1 = n1->next; ++middlePos; } // Until now I just find the middle return palindromeStart(head, n1, 0, middlePos); } int main() { Node* n = new Node(1); Node* n1 = new Node(4); Node* n2 = new Node(4); Node* n3 = new Node(1); Node* n4 = new Node(1); n->next = n1; n1->next = n2; n2->next = n3; n3->next = nullptr; //n3->next = n4; //n4->next = nullptr; std::cout << isPalindrome(n); } 

Answer 9

I think that the optimal solution would be NOT to use the extra space, that is, NOT to use the new inverse LL ... the idea is to take advantage of the operational stack that uses recursion ... because when the recursion reaches the base case, it will start popping up the stack from the last inserted node, which is the last node LL ... I actually halfway through this and hit the wall .. some of them, like the root and the last node are offset ... see my code

 public LLNode compare(LLNode root) { // // base case, popping opr stack, // this should be the last node on the linked list if (root.next == null) { System.out.printf("Poping stack: %d\n", root.data); return root; } // // push the functions to the opr stack System.out.printf("pushing %d to the stack\n", root.next.data); LLNode last = compare(root.next); System.out.printf("On the way back: %d, root: %d\n", last.data, root.data); return root; } 

And the result is as follows:

 The list looks like this: 1 2 3 4 3 2 1 pushing 2 to the stack pushing 3 to the stack pushing 4 to the stack pushing 3 to the stack pushing 2 to the stack pushing 1 to the stack Poping stack: 1 On the way back: 1, root: 2 On the way back: 2, root: 3 On the way back: 3, root: 4 On the way back: 4, root: 3 On the way back: 3, root: 2 On the way back: 2, root: 1 

If you can understand this, please let me know.

Answer 10

Below is my implementation using vectors. Hope this helps someone.

node.h file as below

 #ifndef node_h #define node_h class LinkedList { private: struct node { int data; node *next; }; node *head; public: LinkedList (); node *createNode (int key); void appendNodeBack (int key); void printList (); bool isPalindrome (LinkedList list); }; #endif 

node.cpp file below.

 #include <vector> #include "node.h" LinkedList::LinkedList ():head(NULL) {} LinkedList::node *LinkedList::createNode (int key) { node *newNode = new node; newNode->data = key; newNode->next = NULL; return newNode; } void LinkedList::appendNodeBack (int key) { node *newNode = createNode (key); //if tree is empty if (head == NULL) { head = newNode; return; } //if tree is not empty //traverse to the last node in the list node *temp = head; while (temp->next != NULL) temp = temp->next; temp->next = newNode; } void LinkedList::printList () { //if tree is empty if (head == NULL) { std::cout << "Tree is empty!\n"; return; } //if tree not empty node *temp = head; while (temp != NULL) { std::cout << temp->data<<"-->"; temp = temp->next; } std::cout << "NULL\n"; } bool LinkedList::isPalindrome (LinkedList list) { node *temp = head; unsigned int count = 0; //push all elements of the list in an array, and count total number of nodes std::vector<int> array; while (temp != NULL) { count++; array.push_back (temp->data); temp = temp->next; } bool check = true; for (unsigned int i = 0, j = array.size() -1; i < j; i++, j--) { if (array.at(i) != array.at(j)) check = false; } return check; } 

main.cpp file below.

 #include <iostream> #include "node.cpp" int main () { LinkedList list; list.appendNodeBack (2); list.appendNodeBack (3); list.appendNodeBack (11); list.appendNodeBack (4); list.appendNodeBack (6); list.appendNodeBack (4); list.appendNodeBack (11); list.appendNodeBack (3); list.appendNodeBack (2); list.printList (); if (list.isPalindrome (list)) std::cout << "List is a palindrome!\n"; else std::cout << "List is NOT a palindrome!\n"; return 0; } 

Answer 11

In java, store the value in a string variable and vice versa using a string builder

 String s = ""; while (node != null){ s = s+ node1.value; node = node.next; } StringBuilder reverseString = new StringBuilder(s); reverseString = reverseString.reverse(); String s1 = new String(reverseString); System.out.println(s.equals(s1)); 

Answer 12

There are several ways to do this. One solution may be as follows:

• Find the middle node in this LinkedList
• Second half reverse
• Then compare it to the first half

This solution has a time complexity of O (n). Here is an example implementation in C #.

  // Returns length of a LinkedList private static int GetLength(Node head) { var length = 0; if (head == null) return length; var runner = head; while (runner != null) { length++; runner = runner.Next; } return length; } // Compares two LinkedLists private static bool Compare(Node head1, Node head2) { // Get Lengths var len1 = GetLength(head1); var len2 = GetLength(head2); if (len1 != len2) return false; var runner1 = head1; var runner2 = head2; while (runner1 != null && runner2 != null) { if (runner1.Data != runner2.Data) return false; runner1 = runner1.Next; runner2 = runner2.Next; } return true; } // Reverse a LinkedList private static Node Reverse(Node head) { if (head == null) return null; Node prev = null; Node next; var current = head; while (current != null) { next = current.Next; current.Next = prev; prev = current; current = next; } return prev; } private static bool IsPalindrome(Node head) { if (head == null) return false; if (head.Next == null) return true; var slowPrev = head; var slow = head; var fast = head; while (fast != null && fast.Next != null) { fast = fast.Next.Next; slowPrev = slow; slow = slow.Next; } Node firstHalf; Node secondHalf; if (fast == null) { secondHalf = slow; slowPrev.Next = null; firstHalf = head; } else { secondHalf = slow.Next; slowPrev.Next = null; firstHalf = head; } return Compare(firstHalf, Reverse(secondHalf)); } 

Answer 13

python program to check incoming list is palindrome linked or not

 class Node: def __init__(self, val): self.data=val self.next=None def rec_palindrome(slow, fast): if fast == None: # Even number of nodes return 0, slow elif fast.next == None: return -1, slow else: res, ptr = rec_palindrome(slow.next, fast.next.next) if res == -1: tmp = ptr.next if tmp.data != slow.data: return 1, None else: return 0, tmp.next elif res == 1: return 1, None elif res == 0: if ptr.data != slow.data: return 1, None else: return 0, ptr.next else: return res, None class LinkedList: def __init__(self): self.head = None def append(self, node): if self.head == None: self.head = node else: cur = self.head while cur.next != None: cur = cur.next cur.next = node def display(self, msg): print(msg) cur = self.head while cur != None: print("%d" %cur.data, end="") if cur.next != None: print("->", end="") else: print("") cur = cur.next def is_palindrome(self): res, ptr = rec_palindrome(self.head, self.head) if res : print("The input list is NOT palindrome") else: print("The input list is palindrome") if __name__ == "__main__": print("Pyhton program to check if the input list is palindrome or not") N = int(input("How many elements?")) llist = LinkedList() for i in range(N): val = int(input("Enter the element of node %d" %(i+1))) llist.append(Node(val)) llist.display("Input Linked List") llist.is_palindrome() example output: pyhton program to check if the input list is palindrome or not How many elements?7 Enter the element of node 112 Enter the element of node 245 Enter the element of node 389 Enter the element of node 47 Enter the element of node 589 Enter the element of node 645 Enter the element of node 712 Input Linked List 12->45->89->7->89->45->12 The input list is palindrome 

Answer 14

I use the stack to store characters to half the point of the list. Then I check the characters in the second half of the list at the top of the stack. Time: O (n), Space: O (n / 2)

 SinglyLinkedList.prototype.isPalindrome = function() { var slow = this.head; var fast = this.head; var stack = []; if(!slow) return false; while(fast.next != null && fast.next.next != null) { fast = fast.next.next stack.push(slow.element); slow = slow.next; } // check for odd or even list. if even, push the current slow to the stack. if(fast.next != null) { stack.push(slow.element); } while(slow.next) { slow = slow.next; if(stack.pop() !== slow.element) return false; } return true; } 

Answer 15

 void reverse(Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; struct Node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } bool compair(Node *t,Node *t2){ Node *p = t; Node *q = t2; while(q && q){ if(p->data==q->data){ p = p->next; q = q->next; } else{ return false; } } if(p==NULL && q==NULL){ return true; } return false; } bool isPalindrome(Node *head) { //Your code here if(head==NULL)return true; Node *slow = head; Node *fast = head; Node *prevSlow; Node *middle = NULL; bool ans=true; if(head && head->next){ while(slow && fast&&fast->next){ prevSlow = slow; slow = slow->next; fast = fast->next->next; } if(fast!=NULL){ middle = slow; slow = slow->next; } prevSlow->next=NULL; Node *secondHalf = slow; reverse(&secondHalf); ans = compair(head,secondHalf); if(middle!=NULL){ prevSlow->next = middle; middle->next = secondHalf; } else{ prevSlow->next = secondHalf; } } return ans; } 

Answer 16

Recursive implementation of the algorithm. The goal is to use a natural recursion stack.

 void solve(Node *curr, Node **head, bool *ans) { if (!curr) return; solve(curr->next, head, ans); if ((*head)->val != curr->val) *ans = false; (*head) = (*head)->next; } bool is_palindrome(Node *l) { bool ans = true; solve(l, &l, &ans); return ans; } 

Answer 17

Cross the passage through the first half and put it on the stack and go through the remaining half and pull it out of the stack at the same time, and check that they are both the same or not. If they are both the same, then this is a palindrome, otherwise not.