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 121 122 123 |
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)); } } |
When you run above program, you will get following output:
|
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.
I love your blog, also Can you please add an article for – Intersection point of two linkedLists, this question is FAQ