leetcode234. 回文链表的通过代码及详细解题思路（附上自己思考过程和理解）

题目描述

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

示例 1:

输入: 1->2 输出: false

示例 2:

输入: 1->2->2->1 输出: 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) { ListNode* fast=head,*low=head,*LastNode=NULL,*NextNode,*NewHead; while(fast)//找本题中的中点，可见下面解释 { low=low->next; fast=(fast->next)?(fast->next->next):(fast->next); } while(low!=NULL)//对后半部分链表反转 { NextNode=low->next; low->next=LastNode; LastNode=low; low=NextNode; } NewHead=LastNode; while(NewHead)//判断反转的后半部分链表是否和未反转的前半部分链表相同 { if(NewHead->val!=head->val) return false; NewHead=NewHead->next; head=head->next; } return true; } };

解题思路

这个题目要求时间复杂度为O(n)，空间复杂度为O(1)。时间复杂度很容易满足，空间复杂度为O(1)就意味着不能使用额外的空间，比如数组，vector，map，set这些都算是额外空间。不能使用额外的数组，就意味着我们要直接在链表上进行操作和判断。刚开始抖机灵，一直在想怎么通过对链表中的值求和，求异或等等来判断是否为回文链表（异或这里是因为刚做了一个leetcode136，通过异或来获得只出现一次的数字，有点启发）。但是最后发现，很难考虑到所有的情况，永远只能通过部分样例。后来看了看别人的思路，其实就是直接在链表上操作，先找到链表的中点值（其实也不是严格意义上的中点）。这里的中点其实是，我们通常认为的中点值的下一个值。可以看下面两个例子，对应了两种回文链表（其实回文链表也就这两种），加粗表示该链表在本题中对应的中点： （1）1->2->2->1 （2）1->2->2->2->1 之所以要这样定义中点，是因为我们后面要反转（reverse）以中点作为初始结点的后半部分链表，然后再循环判断这后半部分链表是否与前半部分链表相同，相同就是回文链表，否则就不是。其实也好理解，我们的回文链表，对应于上面两种情况，第一种肯定就是比较1->2和反转2->1后的链表是否相同；第二种情况就是比较1->2和反转2->1后的链表是否相同。在第二种情况下，最中间的2其实是不需要被比较的，它只是一个分隔结点。