Single Linked List is Palindrome or not

Question

I have a Single Linked List. I want to find that Linked List is Palindrome or not. I have implemented it in One way as 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 am reversing the original Linked List and then comparing Node by Node. If everything is fine then I will return 1 else return 0.

Is there a better algorithm to solve the problem.

Answer 1

In java,Store the value in string variable and reverse using 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 2

the python program to check the input linked list is palindrome 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 3

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 4

Transverse through the first half and put it in stack and traverse the remaining half and pop from the stack simultaneously and check both are same or not. If both are same throughout then it is palindrome, else not.

Answer 5

I think you could get a better solution in terms of having O(1) memory usage and the same O(n) speed. By working with the linked list in place. You don't necessary have to create a reversed copy of the linked list. However this methods destroys the list. You will have to stitch it back into place, but the running time will still be O(n).

The code for the fast version of isPalindrome basically finds the middle of the linked list, then logically chunks the linked list into 2 pieces. It reverses only the first piece in place and compares it with the other piece. The bad part is it destroys the linked list due to the in place reversal on the first linked list chunk. However you can stitch the lists back together in place and still be in O(n) time.

The function to look at is isPalindromeFast. I started but haven't finished stitchlistsbacktogether. You can run the code in Go play here http://play.golang.org/p/3pb4hxdRIp .

Here is full 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 6

I have implemented a solution to this problem using recursion.

Palindrome check of a linked list using recursion:

# NODE consist of value and pointer to the next node
class node():
    def __init__(self,x):
        self.val=x
        self.next=None

list1=node('m')
list1.next=node('a')
list1.next.next=node('d')
list1.next.next.next=node('a')
list1.next.next.next.next=node('m')

# head is declared as a global variable for checking purpose
# i and j will keep track of the linked list length
# for the odd number of nodes i==j
# for the even number of nodes i>j
# we will check until i>=j(EXIT CONDITION)


head=list1
i,j=0,0

def palindrome(list):
    # base condition

    if list is None:
        return 0

    # j variable will keep track of the nodes

    global j
    j+=1
    x = palindrome(list.next)

    #if we get a single FALSE then there is no need to check further
    # we will return FALSE in each case
    if x is False:
        return False
    global head,i
    i+=1
    j-=1

    #EXIT CONDITION

    if i>=j:
        return True
    #if the value is evaluated to be false then return false
    if head.val is list.val:
        head=head.next
        return True
    else:
        return False


print(palindrome(list1))