Palindrome Linked List easy

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

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

Example 2:

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

Steps to Solve

1. Find the middle of the linked list: We use the slow and fast pointer technique. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

2. Reverse the second half of the linked list: We reverse the linked list starting from the middle node.

3. Compare the first half and the reversed second half: We compare the nodes of the first half with the nodes of the reversed second half. If they are all equal, the linked list is a palindrome; otherwise, it's not.

Explanation

The core idea is to divide the linked list into two halves, reverse the second half, and then compare the two halves. This approach avoids the need for extra space to store the entire list. The slow/fast pointer technique efficiently finds the middle without requiring a second pass through the list. Reversing the second half is a standard linked list manipulation technique. Finally, comparing the two halves is a straightforward element-by-element comparison.

Code (Java)

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) {
        //1. Find the middle of the linked list
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //2. Reverse the second half of the linked list
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        //3. 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;
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list multiple times, but each traversal is linear in time.
• Space Complexity: O(1). We use only a constant amount of extra space to store pointers. The space used is not dependent on the size of the input list.