234. Palindrome Linked List (E)

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false
Example 2:

Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

最直接的方法：

/**
 * 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) {
        vector<int> vec;
        ListNode* node = head;
        while (node) {
            vec.push_back(node->val);
            node = node->next;
        }
        
        int length = vec.size();
        for (int i=0; i<length/2; ++i) {
            if (vec[i] != vec[length-i-1]) 
                return false;
        }
        
        return true;
    }
};

Runtime: 28 ms, faster than 32.70% of C++ online submissions for Palindrome Linked List.
Memory Usage: 15.1 MB, less than 27.09% of C++ online submissions for Palindrome Linked List.

尝试O(1)space解法

/**
 * 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) {
        int n = 0;
        ListNode* node = head;
        while (node) {
            ++n;
            if (node->next)
                node = node->next;
            else
                break;
        }
        ListNode* tail = node;
        
        cout << "1: " << tail->val << endl;
        
        int i = 0;
        node = head;
        ListNode* prev = new ListNode(0, head);
        while (node) {
            ++i;
            if (i < n/2+1) {
                prev = prev->next;
                node = node->next;
            }
            else {
                ListNode* next_ = node->next;
                node->next = prev;
                prev = node;
                node = next_;
            }
        }
        
        cout << "2: " << endl;
        
        node = head;
        ListNode* node_ = tail;
        for (i=0; i<n/2; ++i) {
            cout << node->val << " - " << node_->val << endl;
            if (node->val != node_->val) {
                cout << "3: " << node->val << ", false" << endl;
                delete(prev);
                return false;
            }
            node = node->next;
            node_ = node_->next;
        }
        
        cout << "3: " << node->val << ", true" << endl;
        
        delete(prev);
        return true;
    }
};

cout出来结果都是对的，但是LeetCode弹错

https://leetcode.com/problems/palindrome-linked-list/discuss/487015/addresssanitizer-heap-use-after-free-on-address
其他人好像也遇到这个情况了

看答案：
差不多的意思，但是写的方法巧妙很多了！

https://zxi.mytechroad.com/blog/list/leetcode-234-palindrome-linked-list/

class Solution {
public:
  bool isPalindrome(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
      fast = fast->next->next;
      slow = slow->next;
    }
    // if fast != nullptr, list has odd numbers
    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 = nullptr;
    ListNode* next = nullptr;
    while (head) {
      next = head->next;
      head->next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
};

默写了一遍：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr and fast->next != nullptr and fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast != nullptr and fast->next != nullptr) {
            slow = slow->next;
        }
        
        ListNode* tail = reverseLL(slow);
        while (head != nullptr and tail != nullptr) {
            if (head->val != tail->val) {
                return false;
            }
            head = head->next;
            tail = tail->next;
        }
        
        return true;
    }
private:
    ListNode* reverseLL(ListNode* node) {
        ListNode* prev = nullptr;
        ListNode* curr = node;
        ListNode* next_;
        while (curr) {
            next_ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next_;
        }
        
        return prev;
    }
};

Runtime: 24 ms, faster than 71.98% of C++ online submissions for Palindrome Linked List.
Memory Usage: 14.1 MB, less than 87.04% of C++ online submissions for Palindrome Linked List.