1. 题目描述

problem link

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?

2. 解题

非递归解法

将链表的一半翻转，然后和另一半对比。

struct ListNode {
    int val;
    struct ListNode* next;
};

typedef int bool;
#define true 1
#define false 0

struct ListNode* reverseLL(struct ListNode* head) {
    struct ListNode* res = NULL;

    while (head) {
        struct ListNode* tmp = head->next;
        head->next = res;
        res = head;
        head = tmp;
    }

    return res;
}

bool isPalindrome1(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return true;
    }

    struct ListNode* ptrFast;
    struct ListNode* ptrSlow;
    ptrFast = ptrSlow = head;

    while (ptrFast->next && ptrFast->next->next) {
        ptrFast = ptrFast->next->next;
        ptrSlow = ptrSlow->next;
    }

    // 此时ptrSlow在偏左中间节点
    // 1 2 1
    // 1 2 2 1
    struct ListNode* leftPart = head;
    struct ListNode* rightPart = reverseLL(ptrSlow->next);
    ptrSlow->next = NULL;  // 断开左右部分

    // 比较两个链表
    while (leftPart && rightPart) {
        if (leftPart->val != rightPart->val) {
            return false;
        }
        leftPart = leftPart->next;
        rightPart = rightPart->next;
    }
    
    // 此时要么leftPart是NULL，要么leftPart和rightPart都是NULL，即都是回文数
    return true;
}

递归解法

刚看到这个解法感觉还是很巧妙的，这个递归本质是依次比对第一个和最后一个节点、第二个和倒数第二个节点... ...

bool check(struct ListNode* head) {
    if (head == NULL) {
        return true;
    }
    
    bool isPal = check(head->next) & (temp->val == head->val);
    temp = temp->next;

    return isPal;
}

struct ListNode* temp;
bool isPalindrome(struct ListNode* head) {
    temp = head;
    return check(head);
}

解释一下这个方法，首先注意temp是个全局变量，并且初始化为头节点。而且temp的变化是在递归语句之后的，也就是说直到最深层的递归返回后temp才会被修改，从而实现了最后一个节点和第一个节点比较、倒数第二个节点和第二个节点比较...