Palindrome linked list : 3 Methods

Palindrome linked list problem is asked as: given a singly linked list, find if linked list is palindrome or not. For example,

   1->2->3->3->2->1->NULL is palindrome linked list where as,
   1->3->2->4->2->1->NULL is not a palindrome linked list

By definition of palindrome, a linked list is palindrome if it reads forward and backwards same.

To check if string is palindrome, standard way is to keep to pointers, one moving from left to right and other from right to left and at each point we check if ¬†character at this place match. If at any place they don’t match, we will say string is not palindrome and return. Once two pointers cross each other, we say string is palindrome. Now can we apply that algorithm on linked list? No, because we cannot move backward that is from right to left in case of singly linked list. So what is the way?

Methods to find palindrome linked list

Using stack to find if linked list is palindrome
One way is to put list on stack. Now pop each element from the stack and move forward in original linked list. If all nodes on stack and linked list match, linked list is palindrome.

Palindrome check by reversing linked list
Another way is to reverse the entire linked list into a new linked list and scan both linked list simultaneously in forward direction. If they differ at any point of time, return false. However, this takes O(N) extra space.

We can reduce space required to half by reversing only half of list and compare that will other half. Even we can do away with n/2 extra space by reversing half of list in place and find if list is palindrome and then again reverse half part of linked list.

1. Get to the middle of linked list
2. Reverse the second half of list
3. Compare first half and second half
   3.a If both are identical, list is palindrome
   3.b If both are not identical, list are not palindrome

In above algorithm, there is one catch. What if number of nodes in linked list is odd, then middle node should not be considered as part of any sublist. How can we find if there are odd number of nodes? Well, when we are traversing list to find middle node, if fast pointer is not null, then there are odd number of node.

#include<stdio.h>
#include<stdlib.h>
 
#define true 1
#define false 0
 
typedef struct Node {
  int data;
  struct Node * next;
} Node;
 
Node * createNode(int val){
  Node * newNode = (Node *)malloc(sizeof(Node));
  if(newNode){
    newNode->data = val;
    newNode->next = NULL;
  }
  return newNode;
}
 
/* 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 compareTwoLinkedLists(Node *L1, Node *L2){
	while(L1 && L2){
		if(L1->data != L2->data) return false;
		L1 = L1->next;
		L2 = L2->next;
	}
	if(!(L1 && L2))
		return true;
 
	return false;
}
 
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;
}

Recursive method to find if list is palindrome linked list

Recursive method is quite interesting, in this we have two pointers, one moving forward and other moving backward. As we have seen in couple of problems here and here, how can we move a pointer backward in linked list using recursion. How and when to move forward pointer? We need to compare first node of list with last of list; 2nd with n-1th and so on till backward and forward pointers cross each other.

Forward pointer will be at head till the time we reach at the end of list. Once we are at last node, we can compare first and last node and recursion starts unwinding. Recursive call which had previous to last node should be comparing 2nd node and so on, hence as recursion starts unwinding, move forward¬†pointer ahead. And since updated value of that pointer is needed in calling function, use and pass reference to it. Advantage of this method is that we don’t need to modify linked list at any time.

1. Start with two pointers forward and backward
2. Till there are nodes in list
   2.a move backward pointer ahead and keep forward constant
3. Once reached at end
   3.a compare forward with backward pointer, if not equal, return false
   3.b else move forward pointer ahead
#include<stdio.h>
#include<stdlib.h>
 
#define true 1
#define false 0
 
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 forward 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;
}

Notice that we defined a function isPalindromeRecursiveMethod() and then a Util function. This is very good practice because your main method need not worry about how internals of recursive function are implemented, it only passes head pointer and gets the dissuader output. This is typical case of abstraction of information.
Execution of above program:
Palindrome linked list implementation
Time complexity of palindrome linked list check algorithm using approach 2 is O(N) and space complexity is O(1). Method 3, that is recursive method has time complexity of O(n) and implicit space complexity of O(n).

To see more problems on linked lists, please refer : Linked list problems

please share if there is something missing or wrong. If you are interested to contribute to website, please contact us and earn money.

  • Pingback: Amazon interview experience 5 | Algorithms and Me()

  • Sree Ranjini

    The logic for “/* Now there are two loops. one for check even length linked list and

    other for odd number of nodes in linked list */” is incorrect . If you consider mid as same number before and after

    eg. 1-2-23-23-23-2-1 is a palindrome , but above code will print 0

    Above code can be changed to have only 1 piece of code to solve both odd/even sequence and also correcting back to original list

    // reverse count nodes
    Node * next = reverse_count_1(head, count);
    Node* secondhalf = next; //—-> store this for rejoining

    /* Now there are two loops. one for check even length linked list and
    other for odd number of nodes in linked list */
    Node* curr = current;

    if (count & 1) curr = current->next; //———> if odd, ignore mid
    bool isPalindrome = true;
    while (next){
    cout << "Comparing " <data << " and " <data <data == next->data){
    curr = curr->next;
    next = next->next;
    }
    else
    {
    isPalindrome = false; break;
    }
    }
    next = reverse_count_1(current, count); //———–>correct back to original sequnce
    current->next = secondhalf;

    return isPalindrome;