Home Linked List How will you check if a Linked List is palindrome or not?

How will you check if a Linked List is palindrome or not?

by nikoo28
2 comments

Question: Write a program to check if the given Linked List is a palindrome or not?

Input:
1.> 4, 8, 15, 16, 23, 42
2.> 4, 8, 15, 16, 15, 8, 4

Output:
1.> IS NOT A PALINDROME
2.> IS A PALINDROME

What is a Palindrome?

According to Wikipedia, A palindrome is a word, phrase, number, or other sequence of symbols or elements, whose meaning may be interpreted the same way in either forward or reverse direction.

Thus, numbers like 121, 1331, 98711789 are palindromes.

Similarly, Linked Lists can be palindromes when they remain the same when read from the forward direction or the backward direction.

To check if a Linked List is a palindrome, we can perform the following operations on the Linked List.

  • Get the middle of the Linked List
  • Separate the two lists.
  • Reverse the second half of the Linked List.
  • Compare the first and the second half.
  • If both the halves are same, then the list is a palindrome.

We have discussed, how to get the middle of a Linked List in this post.

Once we get the middle of the Linked List we separate the lists. If the list is ODD, we ignore the center node, as it will node play a part in being a palindrome, 121, 14541, 198303891 are some examples and here 2, 5, 0 do not play any part in being a palindrome.

In case of EVEN list, we get the n/2th node, and no change is needed. If list is 1, 2, 3, 3, 2, 1 we get the underlined 3.

Once we get the middle node, we can reverse the List using the method in this post.

Now we compare the Lists, till (count/2) iterations, where count = number of nodes. If at any point of time, the data is not equal, that means the List is NOT PALINDROME, else we can say that the list IS A PALINDROME.

#include<stdio.h>

struct node
{
	int data;
	struct node * next;
};

struct node * findMiddleOfLinkedList(struct node * head)
{
	struct node * slowPtr = head;
	struct node * fastPtr = head;

	while(fastPtr ->next != NULL)
	{
		slowPtr = slowPtr -> next;
		fastPtr = fastPtr -> next;
		if(fastPtr == NULL)
			break;

		fastPtr = fastPtr -> next;
		if(fastPtr == NULL)
			break;
	}
	return slowPtr;
}

struct node * reverseList(struct node * head)
{
    struct node * temp = NULL;
    struct node * nextNode = NULL;
    while(head)
    {
        nextNode = head -> next;
        head -> next = temp;
        temp = head;
        head = nextNode;
    }
    return temp;
}

//function to get the number of nodes
int getCount(struct node * head)
{
	int count = 0;
	while(head)
	{
		count++;
		head = head -> next;
	}
	return count;
}

void printList(struct node * head)
{
	while(head != NULL)
	{
		printf("%d ",head->data);
		head = head->next;
	}
}

// defining a function to determine if a List is a Palindrome or not
int isPalindrome(struct node * head)
{
	int flag = 1;

	// get the count of the List
	int count = getCount(head);

	// variable to get the middle of the List
	struct node * middle = findMiddleOfLinkedList(head);

	// reverse the list from the middle
	middle = reverseList(middle);

	// now "middle" point to the MID of the Linked List
	// "head" points to the start of the Linked List

	// a variable to count the number of iterations
	int step = 0;

	printf("count = %d\n",count);

	// if ODD example = 1335331, count = 7, mid = 5, we need to go till (7/2 = 3)
	// if EVEN example = 123321, count = 6, mid - 3, we need to go till (6/3 = 3)
	while(step < (count/2))
	{
		step++;

		if(head -> data != middle -> data)
		{
			// if there is a mismatch at any point of time, set the flag to FALSE
			flag = 0;
		}

		// advance both the pointers
		head = head -> next;
		middle = middle -> next;
	}

	return flag;
}

struct node * addElement(struct node *head, int number)
{
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = number;
	temp -> next = NULL;
	struct node * temp2 = head;
	while(temp2 -> next != NULL)
		temp2 = temp2 -> next;
	temp2 -> next = temp;
	return head;
}

int main(void)
{
	//creating a list
	struct node * listHead = (struct node*)malloc(sizeof(struct node));
	listHead->data = 1;
	listHead->next = NULL;
	listHead = addElement(listHead, 2);
	listHead = addElement(listHead, 3);
	listHead = addElement(listHead, 4);
	listHead = addElement(listHead, 4);
	listHead = addElement(listHead, 3);
	listHead = addElement(listHead, 2);
	listHead = addElement(listHead, 1);

	if(isPalindrome(listHead))
		printf("IS A PALINDROME");
	else
		printf("IS NOT A PALINDROME");

	return 0;
}

NOTE: This method changes the original Linked List, in order to retain the original list, either make a copy of the original list and then perform the operation, or reverse the middle list once again and rejoin it to the original list.

2 comments

You may also like

2 comments

Mukesh June 3, 2016 - 09:39

I have a better solution..
Get length of the linked list – n.
Traverse the linked list and put all first half n/2 elements in stack.
While traveling next half n/2 elements, compare the element in linked with popped element from stack.
If match occurred then move forward else the print that list is not a palindrom.

Reply
nikoo28 June 3, 2016 - 10:50

Hi Mukesh,

Your solution is also correct. But it requires O(n/2) extra space to create a stack.
Feel free to post the solution here.

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More