CareerCup

. Take fast and slow pointers.
. Find the middle of the linked list. O(n)
/// say Midj
. Then reverse first part of the linked list O(n)
/// say Revj
. Then just compare one by one Midj and Revj. if not matched, just bell out.

Singly linked list, so you use auxiliary data store, a stack works, better, a string works with a special character for separator, like "#".
You simply traverse the linked list and push to the stack, or to the string with "#" , e.g

1 -> 2 -> 3 -> 42 -> 3 -> 2 -> 1

will be encoded as :

1#2#3#42#3#2#1

Now, traverse from left ( head ) again, pop the stack, and match the values.
In case you are using a String, then split the string and then traverse from right.
In case they match always, we have a solution.

Error out in case there is no match.
We can try to be clever and use some x,2x pointer to reach to the middle. But, as of now, that pointer game is pointless.

Solution 1: O(n) ops, O(1) memory

public class ListPalindrome {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        ListNode tail = reverse(slow);
        ListNode forward = head;
        ListNode backward = tail;

        boolean result = true;
        while (backward != null){
            if (forward.payload != backward.payload) {
                result = false;
                break;
            }
            forward = forward.next;
            backward = backward.next;
        }
        // restore list
        reverse(tail);
        return result;
    }

    private ListNode reverse(ListNode start) {
        ListNode tmp, prev = null;
        ListNode run = start;
        while (run != null) {
            tmp = run;
            run = run.next;
            tmp.next = prev;
            prev = tmp;
        }
        return prev;
    }

    public static void main() {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        head.next = second;
        ListNode third = new ListNode(3);
        second.next = third;
        ListNode fourth = new ListNode(2);
        third.next = fourth;
        ListNode fifth = new ListNode(1);
        fourth.next = fifth;
        System.out.println(new ListPalindrome().isPalindrome(head));
    }
}

Solution 2: O(n) ops, O(n) memory, 1 pass

import java.util.Stack;

public class ListPalindrome2 {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        Stack<Integer> s = new Stack<Integer>();

        while (fast != null && fast.next != null) {
            s.push(slow.payload);
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null){
            if (slow.payload != s.pop()) {
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

    public static void main() {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        head.next = second;
        ListNode third = new ListNode(3);
        second.next = third;
        ListNode fourth = new ListNode(2);
        third.next = fourth;
        ListNode fifth = new ListNode(1);
        fourth.next = fifth;
        System.out.println(new ListPalindrome2().isPalindrome(head));
    }
}

module.exports = function (L) {
  var A = [];
  var ptr = L;
  while (ptr.next) {
    ptr = ptr.next;
    A.push(ptr.value)
  }
  for (var i = A.length - 1, ptr = L.next; i > -1; --i, ptr = ptr.next) {
    if (A[i] !== ptr.value) {
      return false
    }
  }
  return true

}

var ans = module.exports({
  next: {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null
      }
    }
  }
});

console.log(ans);

public static boolean isPalindrom (LinkedList str)
	{
		if(str == null || str.isEmpty())
			return false;
		else
		{
			int n = str.size();
			for(int i =0; i<n/2;i++)
			{
				if(str.get(i)!=str.get((n-1)-i))
				{
					return false;
				}
			}
			return true;
		}
	}

Time O(n)

public class Node
    {
        public int Value { get; set; }
        public Node Next { get; set; }
    }

    public class  SinglyLinkedList
    {
        public Node Head { get; set; }
        public Node Tail { get; set; }
        public int Count { get; set; }
    }

public static bool IsPolindrom(SinglyLinkedList list)
        {
            Stack<int> store = new Stack<int>();
            Node current = list.Head;
            for (int i = 0; i < list.Count; i++)
            {
                if (i <= list.Count / 2)
                    store.Push(current.Value);
                else
                {
                    int tmp = store.Pop();
                    if (tmp != current.Value)
                        return false;
                }
                current = current.Next;
            }

            return true;
        }

public static void palindromeElements()
{

LinkedList<int> lln = new LinkedList<int>(new[] { 1,2,3,2,1 });
var head = lln.First;
var last = lln.Last;
while (head!= null && last!=null)
{
if(head.Value==last.Value)
{
head = head.Next;
last = last.Previous;
}
else
{
Console.WriteLine("Not palindrome");
break;
}

}
if(head==null &&last==null)
{
Console.WriteLine("it is palindrome");
}
foreach (var item in lln)
{
Console.Write(item + "\t");
}
Console.ReadKey();

}

O(n) with no extra memory and no need to reverse list
have two pointers pointing at the head
using recursion locate the last element and point one pointer to it
then move the two pointers in opposite direction (with the help of recursion return) checking for equality
Forward pointer has to be a ref pointer for this to work

public class Node
{
    public int data;
    public Node next;
}
public static Boolean isPalindrome(Node list)
{
    Node listCopy = list;
    if (list != null)
    {
        return isPalindrome(ref listCopy, list);
    }
    return false;
}

private static Boolean isPalindrome(ref Node l1, Node l2)
{
    if (l2.next == null)
    {
        return l2.data == l1.data;
    }
    else
    {
        Boolean p = isPalindrome(ref l1, l2.next);
        l1 = l1.next;
        if ((l1 == l2) || (l1 == l2.next))

        {
            return p;
        }

        return (l2.data == l1.data) && p;
    }
}

public static boolean isPalindrom (LinkedList str)
	{
		if(str == null || str.isEmpty())
			return false;
		else
		{
			int n = str.size();
			for(int i =0; i<n/2;i++)
			{
				if(str.get(i)!=str.get((n-1)-i))
				{
					return false;
				}
			}
			return true;
		}
	}