---

1. Problem Summary

You are given the head of a singly linked list.
Your task is to determine whether the linked list represents a palindrome, meaning:

• The sequence of node values reads the same forward and backward.

Important details:

• The linked list must not be modified permanently.
• Values may be positive, negative, or repeated.
• Length may be odd or even.
• A single-node list is always a palindrome.

Example interpretation:
Input:

1 → 2 → 2 → 1

Output:

true

Another example:

1 → 2

Output:

false

---

2. Key Insights

Linked lists do not allow reverse indexing

Unlike arrays, we cannot compare front and back via indices efficiently.

Optimal approach uses:

1. Finding the middle of the list using fast/slow pointers
2. Reversing the second half of the list
3. Comparing first half and reversed second half
4. Optionally restoring the list to original form

Why this works

A palindrome mirrors around the midpoint.

Odd-length lists

Middle element does not need to match anything.

Space-efficient

We avoid copying values into an array to achieve O(1) auxiliary space.

---

3. Approach

Fast/Slow pointer + reverse second half + comparison

Steps:

1. If list has 0 or 1 node → return true immediately.
2. Use fast and slow pointers:
   • fast moves two steps at a time
   • slow moves one step
   • when fast reaches end, slow is at midpoint
3. Reverse the second half starting at slow.
4. Compare node values from:
   • start of list (left side)
   • start of reversed half (right side)
5. If all match → palindrome
6. Optionally re-reverse second half to restore original list
7. Return true or false accordingly.

---

4. Time and Space Complexity

Time Complexity:

O(N)

Finding midpoint + reversing + comparing each takes linear time.

Space Complexity:

O(1)

Reversal done in-place without extra containers.

---

5. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;

        // Find midpoint
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse second half
        ListNode secondHalf = reverseList(slow);

        // Compare halves
        ListNode firstHalf = head;
        ListNode checkNode = secondHalf;

        boolean palindrome = true;

        while (checkNode != null) {
            if (firstHalf.val != checkNode.val) {
                palindrome = false;
                break;
            }
            firstHalf = firstHalf.next;
            checkNode = checkNode.next;
        }

        // Optional: Restore the original list
        reverseList(secondHalf);

        return palindrome;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }

        return prev;
    }
}

---

6. Dry Run Examples

Example 1

Input:

1 → 2 → 2 → 1

Step-by-step:

• slow ends at first 2 (second half start)
• second half becomes:

2 → 1

• compare:
  1 == 1
  2 == 2
• all matched

Output:

true

---

Example 2

Input:

1 → 2

slow lands on 2
reverse half = 2
compare:
1 != 2

Output:

false

---

Example 3

Input:

1 → 2 → 3 → 2 → 1

Odd length:

• slow ends on middle 3
• reverse second half:

2 → 1

• compare:
  1 == 1
  2 == 2

Output:

true

---

Example 4

Input:

7

Single node → palindrome

Output:

true

---

Example 5

Input:

1 → 1 → 1 → 1

All equal → always matches

Output:

true

---

7. Why This Solution Works

• Midpoint detection splits list efficiently
• Reversal enables backward comparison without extra storage
• Only values compared, structure remains intact
• Supports odd and even lengths seamlessly
• O(1) space solution is optimal for linked list constraints

---

8. Common Mistakes

1. Copying values into an array (works but O(N) extra space)
2. Reversing entire list instead of second half only
3. Incorrect midpoint handling for odd-length lists
4. Forgetting to move both pointers in comparison step
5. Not restoring list when required in production environments