Scribd
Upload
22 views

Singly Linked List

This document contains Java code to check if a linked list is a palindrome by comparing the first half of the list to the second half of the list reversed. It defines a LinkedList class with a Node inner class. The ispalindrome method uses fast and slow pointers to find the middle of the list, reverses the second half, and compares the two halves by iterating through both lists simultaneously.

Uploaded by

VIJAY V
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
22 views

Singly Linked List

This document contains Java code to check if a linked list is a palindrome by comparing the first half of the list to the second half of the list reversed. It defines a LinkedList class with a Node inner class. The ispalindrome method uses fast and slow pointers to find the middle of the list, reverses the second half, and compares the two halves by iterating through both lists simultaneously.

Uploaded by

VIJAY V
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

import java.util.

Scanner;
class LinkedList
{
Node head;
Node slow_ptr,fast_ptr,second_half;
class Node
{
int data;
Node next;
Node(int d)
{
data=d;
next=null;
}
}
boolean ispalindrome(Node head)
{
slow_ptr=head;
fast_ptr=head;
Node prev_of_slow_ptr=head;
Node midnode=null;
boolean res=true;
if(head !=null && head.next !=null)
{
while(fast_ptr !=null && fast_ptr.next !=null)
{
fast_ptr=fast_ptr.next.next;
prev_of_slow_ptr=slow_ptr;
slow_ptr=slow_ptr.next;
}
if(fast_ptr !=null)
{
midnode=slow_ptr;
slow_ptr=slow_ptr.next;
}
second_half=slow_ptr;
prev_of_slow_ptr.next=null;
reverse();
res=comparelists(head,second_half);
reverse();
if(midnode !=null)
{
prev_of_slow_ptr.next=midnode;
midnode.next=second_half;
}
else
prev_of_slow_ptr.next=second_half;
}
return res;
}
void reverse()
{
Node prev=null;
Node next;
Node current=second_half;
while(current!=null)
{
next=current.next;
current.next=prev;
prev=current;
current=next;
}
second_half=prev;
}
boolean comparelists(Node head1,Node head2)
{
Node temp1=head1;
Node temp2=head2;
while(temp1 !=null && temp2 !=null)
{
if(temp1.data == temp2.data)
{
temp1=temp1.next;
temp2=temp2.next;
}
else
return false;
}
if(temp1==null && temp2==null)
return true;
return false;
}
public void push(int new_data)
{
Node new_node=new Node(new_data);
new_node.next=head;
head=new_node;
}
}
public class ListDriver
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
LinkedList b=new LinkedList();
int val=sc.nextInt();
int a[]=new int[val];
for(int i=0;i<val;i++)
{
a[i]=sc.nextInt();
b.push(a[i]);
}
if(b.ispalindrome(b.head) != false)
{
System.out.println("1");
}
else
{
System.out.println("0");
}
}
}

You might also like