Check if the linked list is palindrome

Given a singly linked list, find whether it’s a palindrome are not

Palindrome : an integer or a string that reads the same backwards as forwards.

Example

Algorithm

Time Complexity : O(n)

Step 1 : Get the middle of the given linked list.

a)    Create two dummy linked lists (fast and slow).
b)    Slow and fast are copies of given linked lists.
c)    Traverse through the lists such that until fast->next = null move two positions in fast and one position in slow.
d)    return slow.
Returns pointer of the mid node.

Step 2 : Reverse the left part of the linked list using reverse linked list function.
ReverseLinkedlist(middle)

Step 3 : compare the left and right parts of the linked lists by creating a function ispalindrome which takes the full linked list and reversed left part.

a)    If the left part is identical to the right part, print is palindrome
b)    Else, Not a palindrome.

Algorithm working example

C++ Program

#include <bits/stdc++.h>
using namespace std;

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


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}


void reverseListIteratively(struct LL **head)
{
	struct LL *temp=NULL,*prev=NULL,*curr=*head;
	while(curr!=NULL)
	{
    temp=curr->next;
	curr->next=prev;
	prev=curr;
	curr=temp;
	}
  *head=prev;
	//O(number of nodes)
}

struct LL* middleOfList(struct LL**head)
{
	
	struct LL*slow=*head,*fast=*head;
	while(fast&&fast->next)
		{
			slow=slow->next;
			fast=fast->next->next;
		}
	return  slow;
	//O(number of nodes)
}


void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}

bool isPalin(struct LL *head, struct LL *middle)
{
	
	while(middle != NULL)
	{
		if(middle->data != head->data)
			return false;
		head = head->next;
		middle = middle->next;
	}
	
	return true;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,23);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,16); // uncomment to check and see that it is a palindrome
	insertAtBeginning(&head,12);
	insertAtBeginning(&head,49);
	insertAtBeginning(&head,23);
	
	cout<<"Given List is :-\n";
	display(&head);
	
	struct LL * middle = middleOfList(&head);
	reverseListIteratively(&middle);
	
	if(isPalin(head,middle))
		cout<<"\nGiven list is a palindrome\n";
	
	else
		cout<<"\nGiven list is not a palindrome \n";
	
	return 0;
}

Translate »