18. Check if linked list is palindrome

18. Check if linked list is palindrome


Problem link :- click here


package Linked_List;

public class LinkedList__18
{
	/*
	 	Given a singly linked list of size n of integers. The task is to check if the 
	 	given linked list is palindrome or not.
	 	
	 	
	 	1 -> find the middle node of the list 
	 	2 -> reverse the second linked list(from node next to middle)
	 	3 -> now check if both the linked lists are same
	 	4 -> reverse the second list back 
	 	5 -> return if true or not
	 */
	
	static Node middleNode(LinkedList list)
	{
		if(list.head == null)
			return list.head;
		
		Node fast = list.head;
		Node slow = list.head;
		while(fast.next != null   &&   fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}
		
		return slow;
	}
	
	static Boolean isPalindrome(LinkedList list)
	{
		//step 1 :-
		Node mid = middleNode(list);
		
		//now our first sub-list is from head to mid 
		// and second sub-list is from mid.next to last node
		Node head1 = list.head;
		Node head2 = mid.next;
		
		//step 2 :- 
		head2 = reverseAPart(list, head2);
		
		//step 3 :-
		Boolean ans = true;
		if(list.size%2 == 0)
		{
			while(head1 != mid.next   &&   head2 != null)
			{
				if(head1.data != head2.data)
				{
					ans = false;
					break;
				}
				head1 = head1.next;
				head2 = head2.next;
			}
		}
		else
		{
			while(head1 != mid    &&   head2 != null)
			{
				if(head1.data != head2.data)
				{
					ans = false;
					break;
				}
				head1 = head1.next;
				head2 = head2.next;
			}
		}
		//now we have checked if the given list is palindrome or not
		
		//step 4 :- 
		head2 = reverseAPart(list, head2);
		
		//step 5 :-
		return ans;
	}
	
	static Node reverseAPart(LinkedList list, Node start)
	{
		Node prev_start = list.head;
		for(prev_start=list.head; prev_start.next!=start; prev_start=prev_start.next)
		{}
		
		Node prev = null;
		Node cur = start;
		Node next = null;
		
		while(cur != null)
		{
			next = cur.next;
				
			cur.next = prev;
				
			prev = cur;
			cur = next;
		}
		prev_start.next = prev;
		
		return prev;
	}
	
	
	//METHOD 2 
	static void reverse(LinkedList list)
	{
		if(list.head == null   &&   list.head.next == null)
			return;
		
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		next = cur.next;
		
		while(cur != null)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
		}
		list.head = prev;
	}
	
	static Boolean isAPalindrome(LinkedList list)
	{
		if(list.head == null   ||   list.head.next == null)
			return true;
		
		reverse(list);
		int num1 = 0;
		int multiplier = 1;
		for(Node temp=list.head; temp!=null; temp=temp.next)
		{
			num1 += temp.data * multiplier;
			multiplier *= 10;
		}
		
		reverse(list);
		int num2 = 0;
		multiplier = 1;
		for(Node temp=list.head; temp!=null; temp=temp.next)
		{
			num2 += temp.data * multiplier;
			multiplier *= 10;
		}
		
		if(num1 == num2)
			return true;
		return false;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(2);
		list.push(1);
		
		Boolean ans = isAPalindrome(list);
		if(ans)
			System.out.println("The given list is palindrome ");
		else
			System.out.println("The given list is not a palindrome ");
	}

}

Time complexity :- O(n)
Space complexity :- O(1)

Comments

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree