LeetCode: 234. Palindrome Linked List

LeetCode: 234. Palindrome Linked List

题目描述

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?

解题思路 —— 递归求解

递归地求得当前节点对应的对称节点，比较它们的值是否一致。

AC 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
private:
    // time: O(n), space: O(1)
    bool cmpList(ListNode* front, ListNode*& back)
    {
        if(front == nullptr) return true;
        
        if(front->next == nullptr && back->val == front->val)
        {
            back = back->next;
            return true;
        }
        else if(front->next == nullptr && back->val != front->val)
        {
            return false;
        }
        else if(cmpList(front->next, back) == false)
        {
            return false;
        }
        else if(back->val == front->val)
        {
            back = back->next;
            return true;
        }
        else
        {
            return false;
        }
    }
    
public:
    bool isPalindrome(ListNode* head) 
    {
        return cmpList(head, head);
    }
};