java-basics/java-programs/LinkedListCheckPalindrome.java at master · Sethu1910/java-basics · GitHub

History

88 lines (86 loc) · 2.01 KB

Raw

package misc;

/**

* Algorithm:-

* 1) Get the middle of the linked list.

* 2) Reverse the second half of the linked list.

* 3) Check if the first half and second half are identical.

* 4) Construct the original linked list by reversing the second half again and attaching it back to the first half

public class LinkedListCheckPalindrome {

class Node {

int data;

Node next;

public Node(int data) {

this.data = data;

this.next = null;

}

public int size;

public Node head = null;

public Node tail = null;

public void addNode(int data) {

Node node = new Node(data);

if(head == null) {

head = node;

tail = node;

} else {

tail.next = node;

tail = node;

}

size++;

}

public Node reverseList(Node temp) {

Node current = temp;

Node prevNode = null;

Node nextNode = null;

while(current != null) {

nextNode = current.next;

current.next = prevNode;

prevNode = current;

current = nextNode;

}

return prevNode;

}

public void isPalindrome() {

Node current = head;

boolean flag = true;

int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);

for(int i = 1; i < mid; i++) {

current = current.next;

}

Node revHead = reverseList(current.next);

while(head != null && revHead != null) {

if(head.data != revHead.data) {

flag = false;

break;

}

head = head.next;

revHead = revHead.next;

}

if(flag) {

System.out.println("\nLinkedList is Palondrome !!!");

} else {

System.out.println("\nLinkedList is not Palindrome !");

}

public void display() {

Node current = head;

System.out.print("Nodes of Singly linked list: ");

while(current != null) {

System.out.print(current.data + " ");

current = current.next;

}

System.out.println(" ");

}

public static void main(String[] args) {

LinkedListCheckPalindrome linkedList = new LinkedListCheckPalindrome();

linkedList.addNode(1);

linkedList.addNode(2);

linkedList.addNode(3);

linkedList.addNode(2);

linkedList.addNode(1);

linkedList.display();

linkedList.isPalindrome();

}

java-basics/java-programs/LinkedListCheckPalindrome.java at master · Sethu1910/java-basics · GitHub

Expand file tree

Breadcrumbs

LinkedListCheckPalindrome.java

Latest commit

History

Breadcrumbs

LinkedListCheckPalindrome.java

File metadata and controls