Check if singly linked list is Palindrome

There are couple of solution to it :

Method 1 - Using the 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 using slow and fast pointer approach, shown here.
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

Corner cases
When number of nodes are even, the first and second half contain exactly half nodes. The challenging thing in this method is to handle the case when number of nodes are odd. We don’t want the middle node as part of any of the lists as we are going to compare them for equality. For odd case, we use a separate variable ‘midnode’.



Code

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    char c;
    struct Node *next;
}Node;


typedef Node *slist;


slist reverse(slist s)
{
    if(s->next == NULL)
        return s;

    Node *ret = reverse(s->next);

    s->next->next = s;
    s->next = NULL;

    return ret;
}


Node *makeNode(char c)
{
    Node * tmp = calloc(sizeof(Node), 1);
    tmp->c = c;
    return tmp;
}


void print(slist s)
{
    if(s == NULL)
        return;

    printf("%c", s->c);
    print(s->next);
}

/*
Divide the list into two halves using slowfast algo..
reverse the second part
now compare both the parts
incase odd number of elements in the list, second part is the big one
*/


int palindrome(slist s)
{
    Node *prevslow = NULL;
    Node *slow = s;

    Node *fast = s;

    //divide into two parts
    while(fast!=null && fast->next!=null)
    {
        if(fast->next)
            fast = fast->next->next;
        else
            break;

        prevslow = slow;
        slow = slow->next;
    }
    //odd nodes case
    if (fast != NULL)     {  
       midnode = slow;
       slow = slow->next;     
    }
    //slow is second half and prevslow is end of 1st half
    prevslow->next = NULL;

    //reverse the second part
    fast = reverse(slow);

    //to retain the list
    slow = fast;

    //compare two parts
    while(s && fast->c == s->c)
    {
        fast = fast->next;
        s = s->next;
    }

    if((fast == NULL || fast->next == NULL) &&  s == NULL)
        printf("Plaindrome\n");
    else
        printf("Not Plaindrome\n");


    //retain the list back
    prevslow->next = reverse(slow);
}


int main()
{
    slist s = makeNode('s');
    s->next = makeNode('a');
    s->next->next = makeNode('a');
    s->next->next->next = makeNode('a');
    s->next->next->next->next = makeNode('s');

    palindrome(s);

    return 0;
}

Method 3 - Recursion
The following code checks if the given singly linked list is a palindrome using recursion.
Time Complexity: O(n)
Space Complexity: O(n)


Java programs

public boolean isPalindrome()
  {
    Node node = isPalindrome(head, head);
    if(node == null)
      return false;
    return true;
  }
 
  private Node isPalindrome(Node left, Node right)
  {
    if(right == null)
    {
      return left;
    }
   
    left = isPalindrome(left, right.next);
    if(left != null)
    {
      boolean palindrome = left.data == right.data ? true : false;
      if(palindrome)
      {
        left = (left.next != null) ? left.next : left;
        return left;
      }
    }
    return null;
  }

We can also use iterative solution. This is very easy, and hence no code here.

Reference

• http://www.geeksforgeeks.org/function-to-check-if-a-singly-linked-list-is-palindrome/