{"id":1224,"date":"2021-05-09T20:41:45","date_gmt":"2021-05-09T15:11:45","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=1224"},"modified":"2022-07-01T21:09:43","modified_gmt":"2022-07-01T15:39:43","slug":"check-if-a-linked-list-is-palindrome-or-not-in-java","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/","title":{"rendered":"Check If a Linked List is Palindrome or Not in Java"},"content":{"rendered":"\n<p>Hello coders, Welcome to <strong>codingbroz<\/strong> where we help you learn coding concepts. Today we are here to discuss another <strong>coding interview problem on linked list data structure<\/strong>.<\/p>\n\n\n\n<p>Today we are going to discuss a <strong>program to check if a linked list is Palindrome or not<\/strong> !<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<label for=\"ez-toc-cssicon-toggle-item-662ebe9aa3c0a\" class=\"ez-toc-cssicon-toggle-label\"><label class=\"ez-toc-title\">Table of Contents<\/label>\n<span class=\"ez-toc-cssicon\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #0090ff;color:#0090ff\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #0090ff;color:#0090ff\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-662ebe9aa3c0a\" checked \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Prerequisites\" title=\"Prerequisites :\">Prerequisites :<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Problem_Statement\" title=\"Problem Statement :\">Problem Statement :<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Input\" title=\"Input :\">Input :<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Output\" title=\"Output :\">Output :<\/a><\/li><\/ul><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Approach_Check_if_a_linked_list_is_Palindrome_or_not\" title=\"Approach : Check if a linked list is Palindrome or not\">Approach : Check if a linked list is Palindrome or not<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#Program_to_check_if_a_linked_list_is_palindrome_or_not\" title=\"Program to check if a linked list is palindrome or not :\">Program to check if a linked list is palindrome or not :<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/www.codingbroz.com\/check-if-a-linked-list-is-palindrome-or-not-in-java\/#More_Interview_Problems_on_Linked_List\" title=\"More Interview Problems on Linked List\">More Interview Problems on Linked List<\/a><\/li><\/ul><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Prerequisites\"><\/span><strong>Prerequisites :<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Before moving towards solving this linked list problem you need to have knowledge about two linked list concepts. These are as follows :<\/p>\n\n\n\n<ol><li><strong><a href=\"https:\/\/www.codingbroz.com\/find-the-middle-of-a-linked-list\/\" class=\"rank-math-link\">Find Middle of a linked list<\/a><\/strong><\/li><li><strong><a href=\"https:\/\/www.codingbroz.com\/reverse-a-linked-list\/\" class=\"rank-math-link\">How to reverse a linked list <\/a><\/strong><\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Problem_Statement\"><\/span><strong>Problem Statement :<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>You are given an Linked List of Integer, check whether the given linked list is Palindrome or not. (<strong>check if a linked list is Palindrome or not<\/strong>)<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Input\"><\/span><strong>Input :<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>1-&gt;2-&gt;3-&gt;4-&gt;3-&gt;2-&gt;1-&gt;null\n1-&gt;2-&gt;3-&gt;4-&gt;2-&gt;1-&gt;null<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Output\"><\/span><strong>Output :<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>true\nfalse<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Approach_Check_if_a_linked_list_is_Palindrome_or_not\"><\/span><strong>Approach : Check if a linked list is Palindrome or not<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>1. find the middle node\n2. reverse the sub list from next of the middle node\n3. compare each node from sub list 1 and sub list 2\n4. If any node differs then print \"false\" otherwise print \"true\" <\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Program_to_check_if_a_linked_list_is_palindrome_or_not\"><\/span><strong>Program to check if a linked list is palindrome or not :<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import java.util.*;\n\nclass Main {\n    public static class ListNode {\n        int val = 0;\n        ListNode next = null;\n\n        ListNode(int val) {\n            this.val = val;\n        }\n    }\n    \n    public static ListNode midNode(ListNode head){\n        if(head==null || head.next == null)return head;\n        ListNode slow = head;\n        ListNode fast = head;\n        while(fast.next!=null &amp;&amp; fast.next.next!=null){\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        return slow;\n    }\n    \n    public static ListNode reverseList(ListNode head){\n        if(head==null || head.next==null)return head;\n        ListNode prev = null;\n        ListNode cur = head;\n        ListNode nNode = null;\n        \n        while(cur != null){\n            nNode = cur.next;\/\/ backup\n            cur.next = prev;\/\/link\n            prev = cur;\n            cur = nNode;\n        }\n        return prev;\n    }\n    \n    public static boolean isPalindrome(ListNode head) {\n        if(head==null || head.next==null) return true;\n        ListNode mid = midNode(head);\n        ListNode nHead = mid.next;\/\/head of sublist2\n        mid.next = null;\/\/breaking the list in sublist1\n        \n        nHead = reverseList(nHead);\/\/reversing sublist2\n        \n        ListNode c1 = head;\n        ListNode c2 = nHead;\n        boolean res = true;\n        while(c2!=null){\n            if(c1.val!=c2.val){\n                res = false;\n                break;\n            }\n            c1 = c1.next;\n            c2 = c2.next;\n        }\n        \n        return res;\n    }\n\n    public static void main(String[] args) {\n        Scanner scn = new Scanner(System.in);\n        int n = scn.nextInt();\n        ListNode dummy = new ListNode(-1);\n        ListNode prev = dummy;\n        while (n-- > 0) {\n            prev.next = new ListNode(scn.nextInt());\n            prev = prev.next;\n        }\n\n        System.out.println(isPalindrome(dummy.next));\n    }\n}<\/pre>\n\n\n\n<p>The following solution is to<strong> check if a linked list is palindrome or not.<\/strong><\/p>\n\n\n\n<p>Now, Let&#8217;s talk about the <strong>time complexity <\/strong>of the given solution to <strong>check if a linked list is palindrome or not !<\/strong><\/p>\n\n\n\n<p><strong>Time Complexity : <\/strong>n\/2 + n\/2 + n\/2 +n = 5n\/2<\/p>\n\n\n\n<p>If we talk in terms of <strong>Big-O<\/strong>, then the <strong>time complexity<\/strong> of the code is <strong>O(n) <\/strong>and the <strong>space complexity <\/strong>of the code is constant as no extra space has been used.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"More_Interview_Problems_on_Linked_List\"><\/span><strong>More Interview Problems on Linked List<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>Today you learned to <strong>Check if a linked list is palindrome or not.<\/strong> Here are some more <strong>Coding Interview Problems on Linked List data structure <\/strong>you must try. These are as follows :<\/p>\n\n\n\n<ol><li><strong>Fold a Linked List<\/strong><\/li><li><strong>Unfold a Linked List<\/strong><\/li><li><strong>Merge Two sorted Linked list<\/strong><\/li><li><strong>Merge Sort a Linked List<\/strong><\/li><li><strong>Remove Nth from end of linked list<\/strong><\/li><li><strong>Segregate even and odd nodes in a linked list<\/strong><\/li><\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Hello coders, Welcome to codingbroz where we help you learn coding concepts. Today we are here to discuss another coding interview problem on linked list data structure. Today we are going to discuss a program to check if a linked list is Palindrome or not ! Prerequisites : Before moving towards solving this linked list [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[31,422],"tags":[61,144,146],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1224"}],"collection":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/comments?post=1224"}],"version-history":[{"count":7,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1224\/revisions"}],"predecessor-version":[{"id":1239,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/1224\/revisions\/1239"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=1224"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=1224"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=1224"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}