leetcode之234. 回文链表

题目描述：

请判断一个链表是否为回文链表。

示例 1:

> 输入: 1->2
> 输出: false
>

示例 2:

> 输入: 1->2->2->1
> 输出: true
>

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解题思路一：

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        if(head == NULL || head->next == NULL) {
                return true;
        }
        
        // 找到中间的节点
        // p的后面都是需要反转的
        ListNode *p = head;
        ListNode *q = head;
        while(q && q->next) {
                p = p->next;
                q = q->next->next;
            }
        
        //反转
        // ListNode* r = reverseList(p);
        ListNode* pre = p;
        ListNode* r = pre->next;
        pre->next = NULL;
        while(r) {
            ListNode* next = r->next;
            r->next = pre;
            pre = r;
            r =  next;
        }
        
        //比较
        while(head != p)
        {
            if(head->val != pre->val)
            {
                return false;
            }
            
            head = head -> next;
            pre = pre -> next;
                
        }
        
        return true;
        
    }
};

解题思路二：

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        
        if(head == NULL || head->next == NULL) {
                return true;
        }
        
        //找到中间的节点
        // p的后面都是需要反转的
        ListNode *p = findMid(head);
        //反转
        ListNode* r = reverseList(p);
        
        //比较
        while(head != p)
        {
            if(head->val != r->val)
            {
                return false;
            }
            
            head = head -> next;
            r = r -> next;
                
        }
        
        return true;
        
    }
    ListNode* findMid(ListNode* head) {
            if(head == NULL || head->next == NULL) {
                return head;
            }
            
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast && fast->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }
    
    ListNode* reverseList(ListNode* head) {
            if(head == NULL || head->next == NULL) {
                return head;
            }
            ListNode* pre = head;
            ListNode* cur = pre->next;
            pre->next = NULL;
            while(cur) {
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            
            return pre;
        }  
};

解题思路三：

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head) return true;
        vector<int> buf;
        while(head) {
            buf.push_back(head->val);
            head = head->next;
        }
        int n = buf.size();
        int i = 0; int j = n-1;
        while(i<j){
            if(buf[i]!=buf[j]) return false;
            i++; j--;
        }
        return true;
    }
};