题目解析

题目简述：判断一个单向链表是否是回文链表
题目简析：在解题之前，我们首先需要理解题目的含义。首先需要理解什么是回文链表。回文一词最初出现在文学作品中，下面是维基百科给出的回文的定义。

回文，亦称回环，是正读反读都能读通的句子，亦有将文字排列成圆圈者，是一種修辭方式和文字游戏。

上面定义可能不太容易理解，简单的可以理解为正读和反读都一样的句子。为了便于理解下面给出几个简单例子。

上海自来水来自海上
黄山落叶松叶落山黄

回文链表的概念与此类似，也就是正想和反向遍历，序列一样的链表。如图1是一个回文单向链表的具体示例，该链表如果进行正向遍历结果为1->2->3->2->1。如果进行反向遍历，则结果仍然为1->2->3->2->1。因此，我们认为这个链表是回文链表。

图1 回文单向链表

从图中可以看出，如果分别从首尾进行遍历，并且元素值相等的话，那么可以判定这个链表是回文链表。具体如上图暗灰色虚线表示的对应关系。如果存储数据的数据结构是双向链表或者数组的话，那么问题就很容易解决，但是问题在于本题要求的是单向链表。因此，这就限制了我们遍历的方向只能从头到尾，而无法反向遍历。

常规解题思路

根据前面对题目的分析，我们很容易想出一个常规的解题思路。那就是将上述单向链表的数据存储在数组当中，然后再判定数组中的数据是否为回文。如果数组中的数据是回文，那就可以判定单向链表是回文链表了（将原有数据结构转换为方便解题的其它数据结构是解决算法问题的常见方法，后续还有类似的题目）。
有了上面的解题思路，我们可以很容易的写出如下代码实现（C语言）。整个代码逻辑分为3步，分别如下：

1. 计算单向链表的长度
2. 根据链表长度分配数组的存储空间，并通过链表初始化数组
3. 根据数组元素判断链表是否为回文

bool isPalindrome(struct ListNode* head){
    int len = 0;
    int index = 0;
    int mid = 0;
    struct ListNode* cur = NULL;
    int* data = NULL;
    
    //计算链表的长度
    cur = head;
    while(cur) {
        len ++;        
        cur = cur->next;
    }
    
    //分别数组空间，将链表转换为数组
    data = malloc(len * sizeof(int));
    if (data == NULL) {
        return false;
    }
    memset(data, 0, len * sizeof(int));
    
    cur = head;
    index = 0;
    while(cur) {
        data[index] = cur->val;
        cur = cur->next;
        index ++;
    }
    
    //根据数组内容判断是否为回文
    mid = len / 2;
    for (int i = 0; i< mid; i++) {
        if (data[i] != data[len-i-1]) {
            return false;
        }
    }
    
    return true; 
}

时间复杂度的优化

上述算法虽然逻辑清晰，但有2个缺点，一个是需要分配等量的辅助存储空间，另外一个是需要遍历2次链表，及一次数组遍历。因此，无论是在空间复杂度还是时间复杂度上都不能说是最优的。这种情况下，面试官可能不会满意目前的答案。
观察链表的内容我们可以看出前半部分与后半部分的内容的顺序正好是相反的。如果我们把前半部分压栈，并在遍历后半部分的时候逐个出栈，那么正好可以实现前半部分和后半部分的对比。

图2 基于栈的实现
这里面关键的一点是找到链表的中间位置，具体方法可以使用快慢指针的方法。也就是快指针每次走2步，慢指针每次走1步，这样当快指针走到结尾的时候，慢指针正好在链表的中间位置。这里需要注意边界条件，也就是链表节点数量为奇数和偶数时的处理上要注意，避免错误。
由于C语言本身没有栈这种数据结构，因此我们用C++中的标准库实现该函数，具体代码如下：

class Solution {
public:
    bool isPalindrome(ListNode* head) {
         stack<ListNode*>stack;
         ListNode* slow=head;
         ListNode* fast=head;
         
         //0个节点或是1个节点
         if(fast==NULL||fast->next==NULL)
             return true;
         //将链表的前半部分入栈
         stack.push(slow);
         while(fast->next!=NULL&&fast->next->next!=NULL)
         {          
             fast = fast->next->next;
             slow = slow->next;
             stack.push(slow);
         }
        
         //链表长度为偶数
         if(fast->next!=NULL)
             slow = slow->next;
         
        //从链表后半部分开始，逐个出栈，并与链表的后半部分进行对比
         ListNode* cur=slow;
         while(cur != NULL)
         {
             ListNode* sp = stack.top();
             stack.pop();
             if(cur->val != sp->val)
                 return false;
             cur = cur->next;
         }
         return true;
    }   
};

上述算法只对链表遍历了一次，相对前一种方法在时间复杂度方面做了很大的优化。

存储空间的优化

上面解法比较直观，但最大的问题是需要额外的存储空间。如果回文链表的数据量较大，上述解法的效率就差很多。或者面试官要求不能够使用太多辅助空间，那么上述解决方法就不满足面试官的要求。
链表反转大家应该都有所了解，这个也是一个常见的面试题。因此，我们可以将链表的前半部分或者后半部分进行反转操作，然后进行对比即可。如下是该算法的C语言实现。

struct ListNode* reverse(struct ListNode* head){
    
    if(!head){
        return NULL;
    }
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *next = NULL;
    
    while(cur){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
 
bool isPalindrome(struct ListNode* head) {
    
    if(head == NULL || head->next == NULL)
        return true;
    
    struct ListNode *fast = head , *slow = head;
    
    /*通过以下程序，快指针fast指向链表最后一个结点（奇数）或者倒数第二个结点（偶数）*/
    while(fast->next != NULL && fast->next->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
 
    slow = slow->next;
    slow = reverse(slow);  //将链表的后半段反转
    
    /*将链表反转后的后半段与前半段比较，奇数长度的话其实比较的是slow之前和之后的结点*/
    while(slow)
    {
        if(slow->val != head->val)         
        {
            return false;
        }
        slow = slow->next;
        head = head->next;
    }
    return true;
}

上述方法破坏了原始链表，大家考虑一下，如果不破坏原始链表，应该如何解决。