{"id":4534,"date":"2021-08-30T09:03:03","date_gmt":"2021-08-30T09:03:03","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4534"},"modified":"2022-06-15T11:29:37","modified_gmt":"2022-06-15T11:29:37","slug":"check-if-a-linked-list-of-strings-forms-a-palindrome","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/","title":{"rendered":"Check if a linked list of strings forms a palindrome"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\" alt=\"\" \/><\/p>\n<h3>Introduction<\/h3>\n<p>The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.<\/p>\n<\/p>\n<h3>Problem Statement<\/h3>\n<p>In this problem, we are given a singly linked list of strings. We have to check whether the given data is palindrome or not.<\/p>\n<h3>Problem Statement Understanding<\/h3>\n<p>Let\u2019s try to understand the problem statement with the help of examples.<\/p>\n<p>Suppose the linked list is:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/input-17.png\" alt=\"\" \/><\/p>\n<p>and now, according to the problem statement, we have to determine whether this linked list of [strings is a palindrome](https:\/\/prepbytes.com\/blog\/linked-list\/check-if-a-doubly-linked-list-of-characters-is-palindrome-or-not\/ &#8220;strings is a palindrome&#8221;) or not.<\/p>\n<ul>\n<li>So now, to check the above linked list for palindrome we will have to combine the data of all the nodes, and after combining, we will get a string, and then we will have to check whether this string is a palindrome or not.<\/li>\n<li>So for the above linked list, the resultant string is <strong>aabbaa<\/strong> as we can see, the resultant string is palindrome, so we will print that it is palindrome.  <\/li>\n<\/ul>\n<p><strong>Output:<\/strong> Palindrome<\/p>\n<p>If the given linked list is a \u2192 cd \u2192 e \u2192 ef \u2192 a.<\/p>\n<ul>\n<li>After combining the data of all the nodes for the above linked list, we can see that our resultant string is <strong>acdeefa<\/strong>, which is not a palindrome.<\/li>\n<\/ul>\n<p><strong>Output:<\/strong> Not a Palindrome<\/p>\n<h5>Some more examples<\/h5>\n<p>Input: cd \u2192 ef \u2192 fe \u2192 dc<br \/>\nOutput: Palindrome<\/p>\n<p>Input: a \u2192 aab \u2192 bce \u2192 f<br \/>\nOutput: Not a Palindrome<\/p>\n<p>Input: a \u2192 aa \u2192 bbb \u2192 bbb \u2192 aa \u2192 a<br \/>\nOutput: Palindrome<\/p>\n<p>I hope from the above examples the problem is clear, and now the main question is how we should approach this problem? <\/p>\n<p><strong>Note:<\/strong> We cannot use the same approach that we often use while checking if a linked list (simple linked list where each node either contains digits (0-9) or characters (a-z, A-Z)) is palindrome or not because here nodes contain strings as values and these strings can be of different length, so the comparison of the last node with the first node, second last node with the second node and so on will not work here.<\/p>\n<p>To overcome the above problem, we will have to create a single string by combining all the list elements and then check if the string is palindrome.<\/p>\n<p>Let us have a glance at the approach by referring the best sites to learn coding.<\/p>\n<h3>Approach<\/h3>\n<p>Our approach will be simple:<\/p>\n<ul>\n<li>We will create a string out of the linked list by traverse the list and appending the value of every node of the list at the end of the string.<\/li>\n<li>Once we have our string constructed, then we will check whether the string is a palindrome or not.\n<ul>\n<li>If the string is a palindrome, it means that our linked list of strings also forms a palindrome. So we will output <strong>Palindrome<\/strong>.<\/li>\n<li>Otherwise, if the string is not a palindrome, then the linked list of strings also does not form a palindrome, so we will output <strong>Not a Palindrome<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Algorithm<\/h3>\n<ul>\n<li>First, we will create an empty string S.<\/li>\n<li>Now, we will traverse the list and append every element of the list at the end of S. In this way, we are constructing the string S. <\/li>\n<li>Now, once we have our string S constructed, we will check if this constructed string is palindrome or not:\n<ul>\n<li>If the constructed string S is a palindrome, it means that our linked list of strings also forms a palindrome. So we will output <strong>Palindrome<\/strong>.<\/li>\n<li>Otherwise, if the constructed string S is not a palindrome, then our linked list of strings also does not form a palindrome, so we will output <strong>Not a Palindrome<\/strong>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h4>To check if a string S is palindrome or not<\/h4>\n<ul>\n<li>We will run a loop from 0 to (length\/2) (<strong>length<\/strong> here denotes the length of the string S). <\/li>\n<li>Inside this loop, we will check whether the i<sup>th<\/sup> character of the string S equals the (length-i-1)<sup>th<\/sup> character of the string S (We are comparing the first and last element, then the second and the second last element, and so on).\n<ul>\n<li>If at any point, these two are not equal, we will return false i.e. the string S is not a palindrome. <\/li>\n<\/ul>\n<\/li>\n<li>Else, at the end of the loop, if all the characters at i<sup>th<\/sup> indexes have matched the characters at (length-i-1)<sup>th<\/sup> indexes during the loop, we will return true.<\/li>\n<\/ul>\n<h3>DRY RUN<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Check-if-a-linked-list-of-strings-forms-a-palindrome-1.png\"><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Check-if-a-linked-list-of-strings-forms-a-palindrome-2.png\"><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_4445 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_4445 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_4445 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_4445 .wpsm_nav-tabs > li.active > a, #tab_container_4445 .wpsm_nav-tabs > li.active > a:hover, #tab_container_4445 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_4445 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_4445 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_4445 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_4445 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_4445 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_4445 .wpsm_nav-tabs > li > a:hover , #tab_container_4445 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_4445 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_4445 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_4445 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_4445 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_4445 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_4445 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_4445 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4445 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_4445 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4445 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_4445 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_4445\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_4445\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4445_1\" aria-controls=\"tabs_desc_4445_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4445_2\" aria-controls=\"tabs_desc_4445_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4445_3\" aria-controls=\"tabs_desc_4445_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_4445\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_4445_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include &lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n\r\nstruct Node\r\n{\r\n    string data;\r\n    Node* next;\r\n};\r\n\r\nbool isPalindromeUtil(string str)\r\n{\r\n    int length = str.size();\r\n\r\n    for (int i=0; i&lt;length\/2; i++)\r\n        if (str[i] != str[length-i-1])\r\n            return false;\r\n  \r\n    return true;\r\n}\r\n\r\nbool isPalindrome(Node *node)\r\n{\r\n\r\n    string str = &quot;&quot;;\r\n    while (node != NULL)\r\n    {\r\n        str+=node-&gt;data;\r\n        node = node-&gt;next;\r\n    }\r\n    return isPalindromeUtil(str);\r\n}\r\n\r\nvoid printList(Node *node)\r\n{\r\n    while (node != NULL)\r\n    {\r\n        cout &lt;&lt; node-&gt;data &lt;&lt; &quot; -&gt; &quot;;\r\n        node = node-&gt;next;\r\n    }\r\n    printf(&quot;NULL&#92;n&quot;);\r\n}\r\n\r\nNode *newNode(const char *str)\r\n{\r\n    Node *new_node = new Node;\r\n    new_node-&gt;data = str;\r\n    new_node-&gt;next = NULL;\r\n    return new_node;\r\n}\r\n\r\nint main()\r\n{\r\n    Node *head = newNode(&quot;a&quot;);\r\n    head-&gt;next = newNode(&quot;ab&quot;);\r\n    head-&gt;next-&gt;next = newNode(&quot;ba&quot;);\r\n    head-&gt;next-&gt;next-&gt;next= newNode(&quot;a&quot;);\r\n  \r\n    if(isPalindrome(head))\r\n    cout&lt;&lt;&quot;Palindrome&quot;&lt;&lt;endl;\r\n    else cout&lt;&lt;&quot;Not a Palindrome&quot;&lt;&lt;endl;\r\n  \r\n    return 0;\r\n}\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_4445_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\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=\"\">\r\nimport java.util.Scanner;\r\n\r\nclass Node\r\n{\r\n    String data;\r\n    Node next;\r\n  \r\n    Node(String d)\r\n    {\r\n        data = d;\r\n        next = null;\r\n    }\r\n}\r\n  \r\npublic class LinkedList_Palindrome\r\n{\r\n    Node head;\r\n\r\n    boolean isPalidromeUtil(String str)\r\n    {\r\n        int length = str.length();\r\n\r\n        for (int i=0; i&lt;length\/2; i++)\r\n            if (str.charAt(i) != str.charAt(length-i-1))\r\n                return false;\r\n  \r\n        return true;\r\n    }\r\n\r\n    boolean isPalindrome()\r\n    {\r\n        Node node = head;\r\n\r\n        String str = &quot;&quot;;\r\n        while (node != null)\r\n        {\r\n            str = str.concat(node.data);\r\n            node = node.next;\r\n        }\r\n\r\n        return isPalidromeUtil(str);\r\n    }\r\n\r\n    public static void main(String[] args)\r\n    {\r\n        LinkedList_Palindrome list = new LinkedList_Palindrome();\r\n        list.head = new Node(&quot;a&quot;);\r\n        list.head.next = new Node(&quot;ab&quot;);\r\n        list.head.next.next = new Node(&quot;ba&quot;);\r\n        list.head.next.next.next = new Node(&quot;a&quot;);\r\n\r\n  \r\n        if(list.isPalindrome())\r\n        System.out.println(&quot;Palindrome&quot;);\r\n        else System.out.println(&quot;Not a Plaindrome&quot;);\r\n  \r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_4445_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass Node:\r\n    def __init__(self, data):\r\n        self.data = data\r\n        self.next = None\r\n\r\nclass LinkedList:\r\n    def __init__(self):\r\n        self.head = None\r\n\r\n    def isPalindromeUtil(self, string):\r\n        return (string == string[::-1])\r\n\r\n    def isPalindrome(self):\r\n        node = self.head\r\n        temp = []\r\n        while (node is not None):\r\n            temp.append(node.data)\r\n            node = node.next\r\n        string = &quot;&quot;.join(temp)\r\n        return self.isPalindromeUtil(string)\r\n\r\n    def printList(self):\r\n        temp = self.head\r\n        while (temp):\r\n            print(temp.data,end=&quot; &quot;)\r\n            temp = temp.next\r\n\r\n\r\nllist = LinkedList()\r\nllist.head = Node('a')\r\nllist.head.next = Node('ab')\r\nllist.head.next.next = Node(&quot;ba&quot;)\r\nllist.head.next.next.next = Node(&quot;a&quot;)\r\n\r\nif llist.isPalindrome():\r\n    print(&quot;Palindrome&quot;)\r\nelse:\r\n    print(&quot;Not a palindrome&quot;)\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_4445 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_4445 a\"),jQuery(\"#tab-content_4445\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<h4>Output<\/h4>\n<p>Palindrome<\/p>\n<p>[forminator_quiz id=&#8221;4444&#8243;]<br \/>\n<strong>Space Complexity:<\/strong> O(s), where s is the size of the string created.<\/p>\n<p>So, in this article, we have tried to explain the most efficient approach to check if a linked list of strings forms a palindrome. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview. Problem Statement In this problem, we are given a singly linked list of strings. We have to check [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-4534","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Check if a linked list of strings forms a palindrome | Linked List | Prepbytes<\/title>\n<meta name=\"description\" content=\"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Check if a linked list of strings forms a palindrome | Linked List | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-30T09:03:03+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-06-15T11:29:37+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Check if a linked list of strings forms a palindrome\",\"datePublished\":\"2021-08-30T09:03:03+00:00\",\"dateModified\":\"2022-06-15T11:29:37+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\"},\"wordCount\":829,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\",\"name\":\"Check if a linked list of strings forms a palindrome | Linked List | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\",\"datePublished\":\"2021-08-30T09:03:03+00:00\",\"dateModified\":\"2022-06-15T11:29:37+00:00\",\"description\":\"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Check if a linked list of strings forms a palindrome\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Check if a linked list of strings forms a palindrome | Linked List | Prepbytes","description":"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/","og_locale":"en_US","og_type":"article","og_title":"Check if a linked list of strings forms a palindrome | Linked List | Prepbytes","og_description":"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.","og_url":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-08-30T09:03:03+00:00","article_modified_time":"2022-06-15T11:29:37+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Check if a linked list of strings forms a palindrome","datePublished":"2021-08-30T09:03:03+00:00","dateModified":"2022-06-15T11:29:37+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/"},"wordCount":829,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/","url":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/","name":"Check if a linked list of strings forms a palindrome | Linked List | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png","datePublished":"2021-08-30T09:03:03+00:00","dateModified":"2022-06-15T11:29:37+00:00","description":"Learn the most efficient way to check if a linked list of strings forms a palindrome. This blog explains the most efficient approach to check if a linked list of strings forms a palindrome.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645012115383-Article_200.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/check-if-a-linked-list-of-strings-forms-a-palindrome\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"Check if a linked list of strings forms a palindrome"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4534","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=4534"}],"version-history":[{"count":8,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4534\/revisions"}],"predecessor-version":[{"id":8519,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4534\/revisions\/8519"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=4534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=4534"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=4534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}