LeetCode //C - 234. Palindrome Linked List

234. Palindrome Linked List

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

Constraints:

• The number of nodes in the list is in the range $[1,10^5]$.
• 0 <= Node.val <= 9

From: LeetCode
Link: 234. Palindrome Linked List

Solution:

Ideas：

1. Find the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half with the reversed second half.
4. If all the values match, it’s a palindrome.
5. Re-reverse the second half to restore the original list (optional).

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool isPalindrome(struct ListNode* head) {
    struct ListNode *fast = head, *slow = head;
    struct ListNode *prev, *temp;

    // Find the middle of the linked list
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    
    // Reverse the second half of the list
    prev = NULL;
    while (slow) {
        temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }
    
    // Compare the first half and the reversed second half
    while (prev) {
        if (head->val != prev->val) {
            return false;
        }
        head = head->next;
        prev = prev->next;
    }

    return true;
}