Palindrome linked list

First of all, what is a palindrome linked list? A linked list is palindrome if you get the same output by traversing it from head to tail or tail to head. For example, below linked list is a palindrome linked list as forward traversal is same as reverse traversal : 3,4,5,5,4,3

Where as this linked list is not palindrome for obvious reasons.

Given a singly linked list, find if linked list is palindrome or not.

This problem will give us more understanding on how to iterate over singly linked list as well as how to handle linked lists in recursive functions. 

If linked list is palindrome : thoughts

What will be the brute force solution for the problem? We can scan the linked first and store the output in an storage. Then we reverse the linked list, and see if order of elements is same as what was in previous traversal.

Complexity of brute force solution is O(n), however, it requires three full traversals of linked list; first forward traversal, then to reverse linked list and then reverse traversal. Also, it require additional O(n) space.

We can put half of the linked list on stack. Traverse remaining half, for each node, same time, pop the node from stack, if data is equal, move forward, else return false. If you reach the end of linked list with stack empty, linked list is palindrome. Complexity is O(n) with additional space complexity of O(n).

What can be better? We are interested in if only half of the linked list, rest half have to be checked w.r.t to first half we they are same of not.

If we divide linked list in two halves exactly at the middle, and reverse first half, then if all the nodes from middle node to end are same as middle to start node, linked list is palindrome.

We have to reverse only half of the linked list.

We traverse linked list to find the size, then reverse half the list, traverse again to check if first half is same as latter half. You have to take middle based on the fact if size of linked list odd or even.
Actually, you can avoid calculating the size, by following the hare and tortoise algorithm to find middle of linked list. Overall complexity is O(n) with no additional space required.

Implementation

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

#define true 1
#define false 0

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

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

/* We are returning next node as it will be required
	in calling function */
Node * reverseList(Node *node){
    Node *current = node;
    Node *prev = NULL;
    Node *next = node;

    while(current){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

int isPalindromeList(Node *head){

    if(!(head && head->next)) return true;

    Node *current = head;
    Node *fast = head;
    Node *prev = NULL;
    Node *midNode = NULL;
    /* We are finding the middle node.*/
    while(fast && fast->next){
        fast = fast->next->next;
        /* We are saving previous node because 
		that will be end of fist list
        in case of even number of nodes */
        prev = current;
        current = current->next;
    }

    /*Check if there are odd number of nodes, if fast pointer is
	null, then there are even number of nodes,
		else it's odd number 
	*/
    if(fast){
    	midNode = current;
    	current = current->next;
    }
    
    //Let's reverse second half of list
    Node *reversedSecondHalfHead = reverseList(current);
    
    //Terminate first linked list
    prev->next  = NULL;
    
    int isPalindrome = compareTwoLinkedLists(head,
							reversedSecondHalfHead);
    
    //Reverse back second half
    current = reverseList(reversedSecondHalfHead);
    
    //If there are odd number of nodes, midNode should not be null
    if(midNode){
    	prev->next = midNode;
    	midNode->next = current;
    }
    else
    	prev->next = current;
    	
    return isPalindrome;
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s", isPalindromeList(head)
		? "true" :"false");
	return 0;
}

Is palindrome linked list : recursive solution

To check if string is palindrome, standard way is to keep two pointers (i and j), i moving from left to right and j moving from right to left.  We check if character at i and j match or not.  If they don’t match, string is not palindrome. If i and j cross each other, string is palindrome.
Can we apply above algorithm on linked list? No, because we cannot move backward in singly linked list. So what is the way? How about simulating the stack using recursive function.

We use two pointers, forward and backward, we move backward pointer ahead till we reach the end of linked list, that will be the terminal condition of recursive function. At any given time after hitting the terminal condition, forward and backward pointers will be n nodes from start and end respectively, where n varies from 0 to n.
We check if content of both pointers are equal or not, if not, then linked list is not palindrome, if yes, linked list is palindrome till those nodes.

Palindrome linked list : implementation

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

#define true 1
#define false 0

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

typedef struct Node {
  int data;
  struct Node * next;
} Node;

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}

/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

int isPalindromeUtil(Node **forward, Node *backward){
	//There are no nodes is lists
	if(!backward) return true;
	
	/*we are recursing moving backward pointer ahead. Backward
	pointer will start moving backward once we hit
	above terminal condition of recursion */
	int isPalindrome = isPalindromeUtil(forward, backward->next);
	
	if(!isPalindrome) return isPalindrome;
	/*At this point forward is n nodes ahead from start and
	backward n nodes away from end n varies from 0 to n 
	Compare forwad and backward
	*/
	if((*forward)->data != backward->data){
		return false;
	}
	//Move ahead forward pointer, backward will move back
	automatically due to recursion
	*forward = (*forward)->next;
	
	return isPalindrome;
}

int isPalindromeListRecursiveMethod(Node *head){
	/* we are starting with forward pointer and backward at head.
	Notice that we passing reference to forward and just pointer
	for backward pointer */
    return isPalindromeUtil(&head, head);
}

int main(void) {
	
	Node *head = NULL;
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 2);
	printf("\nOriginal list :");
	printList(head);
	printf("\nIs list palindrome : %s",
	    isPalindromeListRecursiveMethod(head) ? "true" :"false");
	return 0;
}

Complexity of algorithm to check if linked list is palindrome or not is O(n).

Please share if there is something missing or wrong. If you are interested in receiving study material for your interview preparation, please signup on Algorithms and Me mailing list.