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
Post a Comment