Problem Statement

Given the head of a singly linked list, return true if it is a palindrome

or falseotherwise. (link)

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 10<sup>5</sup>].

• 0 <= Node.val <= 9

Solution

Brute Force Approach

Using Stack

1. Using a Stack:

   • We’ll iterate through the linked list, pushing each node onto the stack.

2. Second Iteration:

   • After storing all nodes in the stack, we’ll iterate through the linked list again (from the head).

   • During this iteration, we’ll compare the current node with the top of the stack.

   • If they match, we continue; otherwise, we return false.

3. Checking for Palindrome:

   • If we successfully iterate through the entire list without any mismatches, we return true (indicating that the linked list is a palindrome).

Time - O(n)

Space - O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode temp = head;
        Stack<ListNode> stack = new Stack<>();

        while(temp!=null){
            stack.push(temp);
            temp = temp.next;
        }

        temp = head;

        while(temp!=null){
            if(stack.pop().val != temp.val) return false;
            temp = temp.next;
        }

        return true;
    }
}

Using string

1. Appending Integers to a String:

   • As we traverse the linked list, we append the integer values of each node to a string.

   • For example, if your linked list contains nodes with values 1, 2, 3, 2, and 1, we create a string like “12321”.

2. Comparing with the Reversed String:

   • After constructing the string, compare it with its reverse.

   • If the original string and its reverse are the same, the linked list is a palindrome.

Time - O(n)

Space - O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode temp = head;

        String val = "";
        while(temp!=null){
            val += temp.val;
            temp = temp.next;
        }

        StringBuilder val2 = new StringBuilder(val);
        val2.reverse();
        return val.equals(val2.toString());
    }
}

Optimal Approach

1. Finding the Middle Node:

   • We traverse the linked list using two pointers: a slow pointer (advancing one node at a time) and a fast pointer (advancing two nodes at a time).

   • When the fast pointer reaches the end of the list, the slow pointer will be at the middle node (or the middle-left node if the list has an odd length).

2. Reversing the Second Half:

   • We reverse the second half of the linked list starting from the middle node.

   • This can be done by reversing the pointers of the nodes in the second half.

3. Comparing First and Reversed Second Halves:

   • Now we compare the first half (from the head to the middle) with the reversed second half (from the middle to the end).

   • If all corresponding nodes have the same value, the linked list is a palindrome.

Middle Node Scenarios

• Even Length

• Odd Length

Code

Time - O(n)

Space - O(1)

class Solution {
    public ListNode reverse(ListNode head){
        if(head==null || head.next==null) return head;
        ListNode temp = head;
        ListNode prev = null;

        while(temp!=null){
            ListNode next = temp.next;

            temp.next = prev;
            prev = temp;

            temp = next;
        }

        return prev;
    }
    public ListNode findMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        while(fast!=null && fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public boolean isPalindrome(ListNode head) {

        ListNode middleNode = findMiddle(head);
        ListNode reversedHead = reverse(middleNode.next);

        ListNode temp1 = head;
        ListNode temp2 = reversedHead;

        while(temp1!=null && temp2!=null){
            if(temp1.val != temp2.val){
                reverse(reversedHead);
                return false;
            }
            temp1 = temp1.next;
            temp2 = temp2.next;
        }

        reverse(reversedHead);
        return true;
    }
}