[LeetCode Road] Palindrome LInked List - Solution/C++

234. Palindrome Linked List

Question:

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

Example:

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

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

Constraints:

The number of nodes in the list is in the range [1, 10⁵].

0 <= Node.val <= 9

Source code

Version 1

Idea:
First, we need to find the middle node, so Fast & Slow pointers can help.
Hence, fast moves two pointers and slow moves one pointers at one time.

And, if the number of nodes is odd in the linked list, the slow pointer will stop at the middle position and it need to shift to next slow = slow->next ; if it is even, the slow pointer will stop at the Null.

There is a simple figure as shown in below:

Between the slow pointer and Null, use reverse() function to get the new linked list. And, compare the each nodes with the head, if it is palindrome, all the nodes's value are the same.

Time complexity: O(n)
Space complexity: O(1)

/**
 * 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) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        
        if(fast) slow = slow->next;
        slow = reverse(slow);
        
        while(slow){
            if(slow->val != head->val) return false;
            slow = slow->next;
            head = head->next;
        }
        return true;
    }
private:
    ListNode* reverse(ListNode* head){
        ListNode* prev = NULL;
        ListNode* curr= head;
        while(curr){
            curr= curr->next;
            head->next = prev;
            prev = head;
            head = curr;
        }
        return prev;
    }
};