{"id":647,"date":"2025-07-15T13:04:32","date_gmt":"2025-07-15T07:34:32","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=647"},"modified":"2025-07-15T13:04:34","modified_gmt":"2025-07-15T07:34:34","slug":"palindrome-linked-list-leetcode-234","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/","title":{"rendered":"Palindrome Linked List | Leetcode 234 | Optimal Solution"},"content":{"rendered":"\n<p>Given the&nbsp;<code>head<\/code>&nbsp;of a singly linked list, return&nbsp;<code>true<\/code><em>&nbsp;if it is a&nbsp;<\/em><em>palindrome<\/em><em>&nbsp;or&nbsp;<\/em><code>false<\/code><em>&nbsp;otherwise<\/em>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/03\/pal1linked-list.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> head = [1,2,2,1]<br><strong>Output:<\/strong> true<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/03\/03\/pal2linked-list.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> head = [1,2]<br><strong>Output:<\/strong> false<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The number of nodes in the list is in the range&nbsp;<code>[1, 10<sup>5<\/sup>]<\/code>.<\/li>\n\n\n\n<li><code>0 &lt;= Node.val &lt;= 9<\/code><\/li>\n<\/ul>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;Could you do it in&nbsp;<code>O(n)<\/code>&nbsp;time and&nbsp;<code>O(1)<\/code>&nbsp;space?<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-2176b429-9926-4bbd-bf6b-509987771ce6\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#0-solution-1-brute-force-approach-using-stack\" style=\"\">Solution 1: Brute Force Approach (Using Stack)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#8-solution-2-optimal-approach-two-pointers-reverse\" style=\"\">Solution 2: Optimal Approach (Two Pointers + Reverse)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#16-key-insights\" style=\"\">Key Insights<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/palindrome-linked-list-leetcode-234\/#17-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-using-stack\">Solution 1: Brute Force Approach (Using Stack)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like reading a book and checking if it&#8217;s the same when you read it backward! One simple way is to write down all the words on pieces of paper, stack them up, then pick them from the top (which gives you the reverse order) and compare with the original book. If they match perfectly, it&#8217;s a palindrome!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>First Pass<\/strong>: Walk through the entire linked list and store all node values in a stack<\/li>\n\n\n\n<li><strong>Second Pass<\/strong>: Walk through the linked list again and compare each node&#8217;s value with values popped from the stack<\/li>\n\n\n\n<li><strong>Stack Magic<\/strong>: Since stack follows LIFO (Last In, First Out), popping gives us values in reverse order<\/li>\n\n\n\n<li><strong>Comparison<\/strong>: If all values match during comparison, it&#8217;s a palindrome<\/li>\n\n\n\n<li><strong>Early Exit<\/strong>: If any value doesn&#8217;t match, return false immediately<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def isPalindrome(self, head: Optional[ListNode]) -&gt; bool:\n        temp = head\n        stack = []\n        \n        # First pass: Store all values in stack\n        while temp is not None:\n            stack.append(temp.val)  # Push current node's value to stack\n            temp = temp.next\n        \n        temp = head  # Reset temp to head for second pass\n        \n        # Second pass: Compare with stack values (reverse order)\n        while temp is not None:\n            if temp.val != stack.pop():  # Compare with stack's top value\n                return False             # Not a palindrome\n            temp = temp.next\n        \n        return True  # All values matched - it's a palindrome!\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">isPalindrome<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: Optional[ListNode]) -&gt; <\/span><span style=\"color: #4EC9B0\">bool<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        stack = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># First pass: Store all values in stack<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            stack.append(temp.val)  <\/span><span style=\"color: #6A9955\"># Push current node&#39;s value to stack<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = head  <\/span><span style=\"color: #6A9955\"># Reset temp to head for second pass<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Second pass: Compare with stack values (reverse order)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> temp.val != stack.pop():  <\/span><span style=\"color: #6A9955\"># Compare with stack&#39;s top value<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><span style=\"color: #D4D4D4\">             <\/span><span style=\"color: #6A9955\"># Not a palindrome<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = temp.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><span style=\"color: #D4D4D4\">  <\/span><span style=\"color: #6A9955\"># All values matched - it&#39;s a palindrome!<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>We use two separate loops here. In the first loop, we visit every node and push its value onto our stack. This stores all values with the last value at the top. In the second loop, we visit each node again and compare its value with the value we pop from the stack. Since stack gives us values in reverse order, we&#8217;re essentially comparing the original list with its reverse. If all values match, we have a palindrome.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>1 -&gt; 2 -&gt; 2 -&gt; 1<\/code><\/p>\n\n\n\n<p><strong>First Pass:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit node 1: stack =&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li>Visit node 2: stack =&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li>Visit node 2: stack =&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n\n\n\n<li>Visit node 1: stack =&nbsp;<a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><a href=\"https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><\/a><\/li>\n<\/ul>\n\n\n\n<p><strong>Second Pass:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit node 1: pop 1 from stack, 1 == 1 \u2713<\/li>\n\n\n\n<li>Visit node 2: pop 2 from stack, 2 == 2 \u2713<\/li>\n\n\n\n<li>Visit node 2: pop 2 from stack, 2 == 2 \u2713<\/li>\n\n\n\n<li>Visit node 1: pop 1 from stack, 1 == 1 \u2713<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;All values matched, return True!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(n) &#8211; We traverse the list twice<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(n) &#8211; We store all values in the stack<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is straightforward &#8211; store everything, then compare with the reverse. It&#8217;s like taking a photo of text and comparing it with the same photo flipped horizontally. Easy to understand but uses extra memory for storage.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-two-pointers-reverse\">Solution 2: Optimal Approach (Two Pointers + Reverse)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Imagine you have a book and want to check if it&#8217;s a palindrome without making copies. Here&#8217;s a clever trick: find the middle of the book, then flip all pages after the middle backward. Now compare the first half with the flipped second half page by page. If they match perfectly, your book is a palindrome!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Find the Middle<\/strong>: Use two pointers (slow and fast) to find the middle of the linked list<\/li>\n\n\n\n<li><strong>Reverse Second Half<\/strong>: Reverse the second half of the linked list<\/li>\n\n\n\n<li><strong>Compare Both Halves<\/strong>: Compare the first half with the reversed second half<\/li>\n\n\n\n<li><strong>Check for Mismatch<\/strong>: If any values don&#8217;t match, it&#8217;s not a palindrome<\/li>\n\n\n\n<li><strong>Restore Original<\/strong>: Optionally reverse the second half back to restore the original list<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro padding-bottom-disabled cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def reverseList(self, head: Optional[ListNode]) -&gt; Optional[ListNode]:\n        prev = None\n        temp = head\n        while temp is not None:\n            front = temp.next    # Store next node\n            temp.next = prev     # Reverse the link\n            prev = temp          # Move prev forward\n            temp = front         # Move temp forward\n        return prev             # Return new head of reversed list\n\n    def isPalindrome(self, head: Optional[ListNode]) -&gt; bool:\n        if head is None or head.next is None:\n            return True         # Empty list or single node is palindrome\n        \n        slow = head\n        fast = head\n        \n        # Find the middle of the linked list\n        while fast.next and fast.next.next:\n            slow = slow.next        # Move slow 1 step\n            fast = fast.next.next   # Move fast 2 steps\n        \n        # Reverse the second half\n        new_head = self.reverseList(slow.next)\n        \n        # Compare first half with reversed second half\n        first = head\n        second = new_head\n        while second is not None:\n            if first.val != second.val:\n                return False    # Values don't match\n            first = first.next\n            second = second.next\n        \n        # Restore original list structure (optional)\n        self.reverseList(new_head)\n        return True\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">reverseList<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: Optional[ListNode]) -&gt; Optional[ListNode]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        prev = <\/span><span style=\"color: #569CD6\">None<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        temp = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> temp <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            front = temp.next    <\/span><span style=\"color: #6A9955\"># Store next node<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp.next = prev     <\/span><span style=\"color: #6A9955\"># Reverse the link<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            prev = temp          <\/span><span style=\"color: #6A9955\"># Move prev forward<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            temp = front         <\/span><span style=\"color: #6A9955\"># Move temp forward<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> prev             <\/span><span style=\"color: #6A9955\"># Return new head of reversed list<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">isPalindrome<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">head<\/span><span style=\"color: #D4D4D4\">: Optional[ListNode]) -&gt; <\/span><span style=\"color: #4EC9B0\">bool<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> head <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> head.next <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><span style=\"color: #D4D4D4\">         <\/span><span style=\"color: #6A9955\"># Empty list or single node is palindrome<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        slow = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        fast = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Find the middle of the linked list<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> fast.next <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> fast.next.next:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            slow = slow.next        <\/span><span style=\"color: #6A9955\"># Move slow 1 step<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            fast = fast.next.next   <\/span><span style=\"color: #6A9955\"># Move fast 2 steps<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Reverse the second half<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        new_head = <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.reverseList(slow.next)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Compare first half with reversed second half<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        first = head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        second = new_head<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> second <\/span><span style=\"color: #569CD6\">is<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">not<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">None<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> first.val != second.val:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">False<\/span><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Values don&#39;t match<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            first = first.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            second = second.next<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Restore original list structure (optional)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.reverseList(new_head)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #569CD6\">True<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution works in multiple steps. First, we find the middle of the list using the two-pointer technique where slow moves 1 step and fast moves 2 steps. When fast reaches the end, slow is at the middle. Then we reverse the second half of the list starting from the node after the middle. Finally, we compare the first half with the reversed second half. If all values match, we have a palindrome. We also restore the original list structure at the end.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<p>Let&#8217;s trace through:&nbsp;<code>1 -&gt; 2 -&gt; 2 -&gt; 1<\/code><\/p>\n\n\n\n<p><strong>Step 1 &#8211; Find Middle:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Initial: slow=1, fast=1<\/li>\n\n\n\n<li>Step 1: slow=2, fast=2 (second occurrence)<\/li>\n\n\n\n<li>Step 2: slow=2, fast=None (fast.next.next doesn&#8217;t exist)<\/li>\n\n\n\n<li>Middle found: slow points to second 2<\/li>\n<\/ul>\n\n\n\n<p><strong>Step 2 &#8211; Reverse Second Half:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Second half starts after slow:&nbsp;<code>1 -&gt; None<\/code><\/li>\n\n\n\n<li>After reversal:&nbsp;<code>1 -&gt; None<\/code>&nbsp;(single node, no change)<\/li>\n<\/ul>\n\n\n\n<p><strong>Step 3 &#8211; Compare:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First half:&nbsp;<code>1 -&gt; 2<\/code><\/li>\n\n\n\n<li>Second half:&nbsp;<code>1<\/code><\/li>\n\n\n\n<li>Compare: 1==1 \u2713, 2==? (second half exhausted)<\/li>\n\n\n\n<li>All matched!<\/li>\n<\/ul>\n\n\n\n<p><strong>Result:<\/strong>&nbsp;Return True!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>&nbsp;O(n) &#8211; We traverse the list a few times but still linear<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(1) &#8211; We only use a few pointer variables<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like folding a paper in half and checking if both sides match perfectly. We find the middle, flip one half, and compare. It&#8217;s more complex to understand but much more memory-efficient since we don&#8217;t need extra storage space.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"16-key-insights\">Key Insights<\/h3>\n\n\n\n<p><strong>Why does the middle-finding work?<\/strong><br>When fast moves 2 steps and slow moves 1 step, fast covers twice the distance. When fast reaches the end, slow is exactly at the middle. It&#8217;s like two people walking where one walks twice as fast &#8211; when the faster person reaches the destination, the slower person is halfway there.<\/p>\n\n\n\n<p><strong>Why reverse only the second half?<\/strong><br>Reversing the second half allows us to compare both halves by moving forward in both. It&#8217;s like flipping one half of a mirror image to see if both sides are identical.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"17-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Stack)<\/td><td>O(n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Learning the concept<\/td><\/tr><tr><td>Two Pointers + Reverse<\/td><td>O(n)<\/td><td>O(1)<\/td><td>Medium<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>two pointers approach<\/strong>&nbsp;is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you&#8217;re first learning about palindrome detection.<\/p>\n\n\n\n<p>Both solutions effectively solve the problem, but the optimal solution showcases advanced linked list manipulation techniques that are valuable for solving many other problems!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given the&nbsp;head&nbsp;of a singly linked list, return&nbsp;true&nbsp;if it is a&nbsp;palindrome&nbsp;or&nbsp;false&nbsp;otherwise. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: head = [1,2,2,1]Output: true Example 2: Input: head = [1,2]Output: false Constraints: Follow up:&nbsp;Could you do it in&nbsp;O(n)&nbsp;time and&nbsp;O(1)&nbsp;space? Solution 1: Brute Force Approach (Using Stack) Intuition Think of this like reading a book and<\/p>\n","protected":false},"author":1,"featured_media":648,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[19,29],"class_list":{"0":"post-647","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-medium","10":"tag-singly-linked-list"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/palindrome-linked-list-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/647","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=647"}],"version-history":[{"count":2,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/647\/revisions"}],"predecessor-version":[{"id":650,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/647\/revisions\/650"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/648"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=647"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=647"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=647"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}