CareerCup

1)Take 2 pointers each pointing to the start node of the singly linked list.
2)Move 1 pointer 1 node at a time and the 2nd pointer 2 nodes at a time. Do this until the 2nd pointer reaches the last node (even number of nodes) or the 2nd last node (odd number of nodes). Take a boolean variable which says whether this linkedlist has an even number of nodes or odd number of nodes in a variable.
3)Now the first pointer points to the mid of the list. Take a stack.
Now point the 2nd pointer to the start node. Put one by one the nodes in the stack. If the boolean variable indicates that the list has odd number of nodes move the 2nd pointer one more node.
Now pop the stack, move 2nd pointer one node and match if they are equal. Go on doing this till end or when get a mismatch.

bool isPalindrome(struct node *head)
{
  struct node *last,*temp;
 temp=head;
 while(temp->next!=NULL)temp=temp->next;
last=temp;
 return checkPalindrome(head,last);
}

bool checkPalindrome(struct node *head,struct node *last)
{ 
 struct node *temp=head;
 if(head==last)
 return true;
 while(temp->next!=last)temp=temp->next;
 if(head-next==last)
 {
  if(head->data==next->data)
  return true;
 else
 return false;
}
  if(head->data==last->data)
  {
    return checkPalindrome(head->next,temp);
  }
 return false;
}

public boolean isPalindrome(Node n, Queue q) {

		if (n == null) {

			return true;
		}

		boolean isPal = true;
		q.enqueue(n);
		isPal = isPalindrome(n.next, q);

		return (n.value == q.dequeue.value) && isPal;
	}

This problem is solvable in O(N) runtime without a stack or queue in C or C++. Here I use manipulation of the first pointer so that each recursive call advances the last pointer and the first pointer simultaneously.

bool isPalindrome(node* head) {
    return checkPalindrone(*head, head);
}

bool checkPalindrome(node** first, node* last) {
    // If last is not the last node then advance last pointer, which
    // also advances first pointer every time a boolean is returned
    if (last->next) {
        node* next_node = last->next;
        if (next_node->next) {
            next_node = next_node->next;
        }
        // Advances first pointer and checks if this is part of palindrome
        if (!checkPalindrome(first, next_node) {
            return false;
        }
    }
    //  Base case is when first and last are same or adjacent, at which point
    // we stop advancing first pointer and check if first and last are equal
    if (*first == last) {
        return true;
    } else if (*first->next == last) {
        return *first->data == last->data;
    }
    // Otherwise check if last and first have same data, then move first node
    if (*first->data == last->data) {
         *first = *first->next;
         return true;
    }
    return false;
}

public class Palindrome
    {
        public bool Check(LinkedListNode<char> head)
        {
            if(head == null)
            {
                throw new ArgumentNullException("Head");
            }
            return CheckHelper(ref head, head);
        }

        private static bool CheckHelper(ref LinkedListNode<char> head, LinkedListNode<char> tail)
        {
            if (tail.Next != null)
            {
                if (!CheckHelper(ref head, tail.Next))
                {
                    return false;
                }
            }

            var temp = head;
            head = head.Next;
            return temp.Value == tail.Value;
        }
    }

bool isListPalindrom(ListNode* head,ListNode**head1)
{
if(!head)
return true;

if (isListPalindrom(head->next,head1) && (head->val== (*head1)->val))
{
*head1 = (*head1)->next;
return true;
}
return false;
}

O(n) time and O(n) memory. Nonrecursively too so it's faster.

static class Node<T>{
    Node next;
    T val;
}

public static <T> boolean isPalendrome(Node<T> head){
    Node<T> runner = head;
    Node<T> endRunner = head;
    Stack<Node<T>> nodesEncountered = new Stack<Node<T>>();
    
    while(endRunner != null){
        endRunner = endRunner.next;
        if(endRunner == null){
            runner = runner.next;
            break;
        }
        nodesEncountered.push(runner);
        runner = runner.next;
        endRunner = endRunner.next
    }
    while(!nodesEncountered.isEmpty()){
        Node<T> old = nodesEncountered.pop();
        if(!old.val.equals(runner.val)){
            return false;
        }
        runner = runner.next;
    }
    return true;
}

A Simple recursive solution in Java.
Take the head pointer recursively all the way to the end of the list.
Then start to compare the pointer returned by each recursive action (Easier to understand while reading the code)
Code will actually double check the palindrome, can be improved to run only half way.

public class LinkedPalindrome{

    // Actual algo is only this method
    private Node solve(Node root, Node p) {
        if (p != null) {
            Node r = solve(root,p.next);
            if (r == null || !r.value.equals(p.value)) {
                return null;
            } else {
                if (r.next == null) {
                    return root;
                } else {
                    return r.next;
                }
            }
        } else
            return root;
    }

    public static class Node {
        final String value;
        Node next;
        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
    public static void main (String ... args) {
        Node root = new Node("a",new Node("b",new Node("c", new Node("b", new Node("a",null)))));
        LinkedPalindrome solver = new LinkedPalindrome();
        System.out.println(solver.solve(root));

    }

    public boolean solve(Node root ) {
        return solve(root,root) == root;

    }
}