Table of Contents
In this post, we will see how to check if linked list is palindrome or not.
Java Linked List Interview Programs:
- How to reverse a linked list in java
- How to reverse a linked list in pairs in java
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java
Algorithm:
- Find middle element of linked list using slow and fast pointer method .
- Reverse second part of linked list
- Compare first and second part of linked list if it matches then linked list is palindrome.
Java Program:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
package org.arpit.java2blog; public class LinkedListPalindromeCheck{ private Node head; private static class Node { private int value; private Node next; Node(int value) { this.value = value; } } public void addToTheLast(Node node) { if (head == null) { head = node; } else { Node temp = head; while (temp.next != null) temp = temp.next; temp.next = node; } } public void printList() { Node temp = head; while (temp != null) { System.out.format("%d ", temp.value); temp = temp.next; } System.out.println(); } // This function will find middle element in linkedlist public static Node findMiddleNode(Node head) { // step 1 Node slowPointer, fastPointer; slowPointer = fastPointer = head; while(fastPointer !=null) { fastPointer = fastPointer.next; if(fastPointer != null && fastPointer.next != null) { slowPointer = slowPointer.next; fastPointer = fastPointer.next; } } return slowPointer; } // Function to check if linked list is palindrome or not public static boolean checkPalindrome (Node head) { // Find middle node using slow and fast pointer Node middleNode=findMiddleNode(head); // we got head of second part Node secondHead=middleNode.next; // It is end of first part of linked list middleNode.next=null; // get reversed linked list for second part Node reverseSecondHead=reverseLinkedList(secondHead); while(head!=null && reverseSecondHead!=null) { if(head.value==reverseSecondHead.value) { head=head.next; reverseSecondHead=reverseSecondHead.next; continue; } else { return false; } } return true; } public static Node reverseLinkedList(Node currentNode) { // For first node, previousNode will be null Node previousNode=null; Node nextNode; while(currentNode!=null) { nextNode=currentNode.next; // reversing the link currentNode.next=previousNode; // moving currentNode and previousNode by 1 node previousNode=currentNode; currentNode=nextNode; } return previousNode; } public static void main(String[] args) { LinkedListPalindromeCheck list = new LinkedListPalindromeCheck(); // Creating a linked list Node head=new Node(1); list.addToTheLast(head); list.addToTheLast(new Node(2)); list.addToTheLast(new Node(1)); list.addToTheLast(new Node(2)); list.addToTheLast(new Node(1)); list.printList(); System.out.println("Linked list palidrome: "+checkPalindrome(head)); } } |
|
1 2 3 4 |
1 2 1 2 1 Linked list palidrome: true |
Time complexity : O(n)
Space complexity : O(1)
Space complexity : O(1)
Please go through java interview programs for more such programs.
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
I love your blog, also Can you please add an article for – Intersection point of two linkedLists, this question is FAQ