Palindrome in LinkedList

Given a linked list with node as given below:

struct node
{
char info;
struct node *next;
}

Give an O(n) algorithm to find if its a palindrome or not? You can not use more than O(1) space.

Two pointers to explore the list, reach the mid-point reverse the first half and compare the two halves

Maze Searching

Given a 2-d maze of characters, find if there exists a word "Algorithms" in the maze. By exists we mean it exists in a row, a column or like snakes (diagonals prohibited though)?

By snakes, we mean like following

A . . . M S
L G . T H .
. O R I . .
Use DFS and explore the maze as and when letters are found