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

UPD: The following algorithm covers only specific case, when node value is represented by pretty small number. Number 31 regulates, how big the shift is. On the other hand number of nodes affect collisions, not sure how many nodes it will be able to serve properly. Int number will definitely be overflown multiple times. So I'd not recommend to use such algorithm in prod. However it may be interesting in some academic purposes.

Yesterday I found the following solution posted by one guy, it works based on hashing, one direct and one reversed. I'm still figuring out possible flaws of it, if there may be any collisions, but it passes on Leet code:

/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
*     var next: ListNode? = null
* }
*/
fun isPalindrome(head: ListNode?): Boolean {
    var mult = 1
    var rez = 0
    var rev = 0
    var curr = head
    while (curr != null) {
        rez = rez * 31 + curr.`val`
        rev += curr.`val` * mult
        mult *= 31
        curr = curr.next
    }
    return rez == rev
}

This approach allows us to keep only 3 numbers in memory, and don't spend any time on reversing

Answer 2

For java, you can use this;

boolean isListPalindrome(ListNode<Integer> l) {
    
    if(l == null || l.next == null)return true;
    
    List<Integer> list = new ArrayList<Integer>();
    List<Integer> revlist = new ArrayList<Integer>();
    
    while(l != null){
        list.add(l.value);
        revlist.add(l.value);
        l = l.next;
    }
    
    Collections.reverse(revlist);
    
    return list.equals(revlist);

}

Answer 3

How about having 2 pointers at the beginning of the link list.setting ptr1=k=start=1 and ptr2 =n where n is total number of nodes in linked list. We can then start with K and compare it with n-k+1 if both are same then increment k and go on comparing till we reach middle of the linked list

Answer 4

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))

Answer 5

This logic (Using Recursive) will work if you have two string objects in LinkedList.

public class LinkedList {
    Node head;
    String s1="",s2="";
    class Node{
        int data;
        Node next;
        Node(int d){
            this.data = d;
            this.next = null;
        }
    }
    public void append(int data){
        Node node = new Node(data);
        if(head==null){
            head = node;
        }else{
            Node cur = head;
            while(cur.next!=null) cur = cur.next;
            cur.next = node;
        }
    }
    public void palindrome(Node node){
        if(node==null){
            return;
        else
            s2+=""+node.data;
        palindrome(node.next);
        s1+=""+node.data;
    }
    public boolean isPalindrome(){
        palindrome(head);
        return s1.equals(s2);
    }
    public static void main(String ss[]){
       LinkedList  list = new LinkedList();
       list.append(10);
       list.append(25);
       list.append(10);
       System.out.println(list.isPalindrome());
   }
}

Answer 6

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 7

Recursive algorithm implementation. The intention is just to make use of the 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 8

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 9

I am using a stack to store the characters until the halfway point of the list. Then, I check the characters in the second half of the list against 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 10

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 11

You can also check it using arrays, First traverse the linklist from its root and store the data field of every node into an array and then reverse that array and then compare both array one by one element. 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 12

There is a couple of ways to do it. One of the solutions can be like below :

1. Find middle node in a given LinkedList
2. Reverse second half
3. Then, compare it to the first half

This solution has O(n) time complexity. Here is a sample 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

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 14

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

A recursive approach can be approached where a pointer pointing to the start of the linked list, & another pointer returning from the recursion from the last will be compared.

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;
}
} 

Call is made like: isPalindrome(&root,root);

Answer 15

Below is my implementation using vectors. Hope it 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 16

I think the optimal solution would be to NOT using extra space, meaning NOT to use a new reversed LL... the idea is to take advantage of the operation stack that recursion uses... because when the recursion had reached the base case, it would start popping the stack from the last inserted node, which is the last node of the LL... I'm actually half way through this and hit a wall.. some how 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 output looks like this:

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 figure it out, please let me know too

Answer 17

Just reverse half of the linked list. And start comparing. You don't need to reverse the whole linked list.

Answer 18

Here is my solution to this problem. To test it I used integers instead of chars forexample I used 1,4,1,4,1 instead "adada". You can change int to char and everything should still be working

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 19

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 20

METHOD 1 (Use a Stack)

A simple solution is to use a stack of list nodes. This mainly involves three steps.

1. Traverse the given list from head to tail and push every visited node to stack.
2. Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
3. If all nodes matched, then return true, else false.

Time complexity of above method is O(n), but it requires O(n) extra space. Following methods solve this with constant extra space.

METHOD 2 (By reversing the list)

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

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Check if the first half and second half are identical.
4. Construct the original linked list by reversing the second half again and attaching it back to the first half

METHOD 3 (Using Recursion)

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

1. Sub-list is palindrome.
2. Value at current left and right are matching.

If both above conditions are true then return true.

The idea is to use function call stack as container. Recursively traverse till the end of list. When we return from last NULL, we will be at last node. The last node to be compared with first node of list.

In order to access first node of list, we need list head to be available in the last call of recursion. Hence we pass head also to the recursive function. If they both match we need to compare (2, n-2) nodes. Again when recursion falls back to (n-2)nd node, we need reference to 2nd node from head. We advance the head pointer in previous call, to refer to next node in the list.

However, the trick in identifying double pointer. Passing single pointer is as good as pass-by-value, and we will pass the same pointer again and again. We need to pass the address of head pointer for reflecting the changes in parent recursive calls.

More: geeksforgeeks

Answer 21

When we compare the linked list to the reversed list, we can only actually need to compare the first half of the list. If the first half of the normal list matches the first half if the reverse list, then the second half of the normal list must match the second half of the reversed list.

Answer 22

Why are you Making it complex. Since this is a home work.i can just give you a simple suggestion. I observe that you are only comparing the id's in your code. let's say your id is a char,why dont you simply traverse the list once and store the char's in an array and then check the for palindrome. your way simply reverses the linked list once and traverse the linked list twice totally there are three traversals in the function.