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

1. Find the middle of the linked list: We'll 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'll reverse the linked list starting from the middle node.

3. Compare the first half and the reversed second half: We'll iterate through the first half and the reversed second half, comparing nodes one by one. If all nodes are equal, it's a palindrome.

Explanation

The algorithm leverages the properties of a palindrome: it reads the same forwards and backward. By finding the middle of the linked list and reversing the second half, we can directly compare the first and reversed second halves for equality. The slow and fast pointer technique efficiently finds the middle without needing to traverse the list twice. Reversing the second half in place avoids using extra space.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 1. Find the middle of the linked list
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 2. Reverse the second half
        ListNode *prev = nullptr, *curr = slow, *nextTemp;
        while (curr) {
            nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }

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

Complexity

• 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.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only use a few pointers to manipulate the list.