Naive Solution: Using an Array

One straightforward approach is to traverse the linked list and store the values in an array. Then, we can use two pointers, one at the beginning and one at the end of the array, to check if the array forms a palindrome.

Steps:

1. Traverse the linked list and store the value of each node in an array.
2. Initialize two pointers: left at 0 and right at array.length - 1.
3. While left < right, compare array[left] and array[right].
   • If they are not equal, return false.
   • Increment left and decrement right.
4. If the loop finishes without finding any mismatch, return true.

Code (Java):

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode current = head;
        while (current != null) {
            list.add(current.val);
            current = current.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (!list.get(left).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list once to copy the values into the array, and then iterate through (at most) half of the array to check for palindrome properties. Thus, O(n) + O(n/2) which simplifies to O(n)
• Space Complexity: O(n), because we store the values of the linked list nodes in an array.

Optimal Solution: Reversing the Second Half

To achieve O(1) space complexity, we can reverse the second half of the linked list and then compare the first half with the reversed second half.

Steps:

1. Find the middle of the linked list using the slow and fast pointer approach.
2. Reverse the second half of the linked list starting from the middle node.
3. Compare the first half of the list with the reversed second half.
4. Reverse the second half again to restore the original list (optional, but good practice).

Code (Java):

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

        ListNode slow = head;
        ListNode fast = head;

        // Find the middle of the linked list
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse the second half
        ListNode prev = null;
        ListNode current = slow;
        ListNode next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }

        // Compare the first half and the reversed second half
        ListNode firstHalf = head;
        ListNode secondHalf = prev;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) {
                return false;
            }
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        return true;
    }
}

Edge Cases

• Empty list: Returns true.
• Single-node list: Returns true.
• List with two nodes: Compares the two nodes.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list to find the middle, reverse the second half, and then compare the two halves.
• Space Complexity: O(1), because we only use a constant amount of extra space for pointers, regardless of the size of the linked list.