LeetCode每日精进：链表的回文结构
题目链接：链表的回文结构
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：1->2->2->1
返回：true
思路一： 创建新链表保存原链表结点，反转新链表，遍历比较原链表结点
由于回文结构的特殊性，反转链表中每个结点对应原链表中结点值相同，即反转链表为原链表的深拷贝。
ListNode* pcur = A;
ListNode *newHead,*newTail;
newHead = newTail = NULL;
//创建新链表,复制原链表
while(pcur)
{
if (newHead == NULL)
{
newHead = newTail = pcur;
}
else{
newTail->next = pcur;
newTail = newTail->next;
}
pcur = pcur->next;
}首先，创建新链表，复制原链表中的结点。
ListNode* n1 = NULL;
ListNode* n2 = newHead;
ListNode* n3 = newHead->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}反转新链表，代码参考反转链表。
ListNode* l1 = A;
ListNode* l2 = n1;
while(l1)
{
if (l1->val != l2->val)
{
return false;
}
l1 = l1->next;
l2 = l2->next;
}
return true;比较新旧链表中对应结点：
若有一个结点值不相同，则返回false。
若结点值均相同，循环结束，则返回true。
完整代码：
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
if (A == NULL)
{
return true;
}
ListNode* pcur = A;
ListNode *newHead,*newTail;
newHead = newTail = NULL;
//创建新链表,复制原链表
while(pcur)
{
if (newHead == NULL)
{
newHead = newTail = pcur;
}
else{
newTail->next = pcur;
newTail = newTail->next;
}
pcur = pcur->next;
}
//反转链表
ListNode* n1 = NULL;
ListNode* n2 = newHead;
ListNode* n3 = newHead->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
//比较新旧链表
ListNode* l1 = A;
ListNode* l2 = n1;
while(l1)
{
if (l1->val != l2->val)
{
return false;
}
l1 = l1->next;
l2 = l2->next;
}
return true;
}
};时间复杂度O(n)，由于创建了新链表，空间复杂度为O(n)，显然不符合题目要求，需要进一步优化。
思路二：投机取巧法
注意到题目所给的链表长度小于等于900，我们可以创建一个可以存放900个整型的数组，将链表的结点值逐一存放在数组中，并用回文数组的判断方式解决，这样就能将空间复杂度降为O(1)。
图示：
int arr[900] = {0};
int size = 0;除了定义数组arr外，再定义size来记录数组中的有效数据个数。
while(pcur)
{
arr[size++] = pcur->val;
pcur = pcur->next;
}遍历链表，将链表中的结点值放在数组中，每放入一次size自增一。
int left = 0;
int right = size - 1;
while(left < right)
{
if (arr[left] != arr[right])
{
return false;
}
left++;
right--;
}最后判断数组是否具有回文结构。
完整代码：
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int arr[900] = {0};
int size = 0;
ListNode* pcur = A;
while(pcur)
{
arr[size++] = pcur->val;
pcur = pcur->next;
}
int left = 0;
int right = size - 1;
while(left < right)
{
if (arr[left] != arr[right])
{
return false;
}
left++;
right--;
}
return true;
}
};时间复杂度O(n)，空间复杂度O(1)
在题目限制链表结点个数的情况下，这种方法符合题目要求，但若链表个数未被限制呢？
思路三：快慢指针找链表的中间结点，将中间结点作为头结点，反转链表
ListNode* slow = A;
ListNode* fast = A;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
定义快慢指针找中间结点，参考链表的中间结点，跳出循环后，此时让slow成为新的头结点。
ListNode* head = slow;
ListNode* n1 = NULL;
ListNode* n2 = head;
ListNode* n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}再让以head为头结点的链表反转。
图示：
链表结点个数为偶数：
链表结点个数为奇数：
最后，判断回文结构：
ListNode* left = A;
ListNode* right = n1; 
定义left与right指针分别指向两侧，左右指针向中间移动判断，当右指针为空，循环结束，返回true。
if (left->val != right->val)
{
return false;
}若左右指针所指向的结点值不同，返回false。
完整代码：
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
//找中间结点
ListNode* slow = A;
ListNode* fast = A;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
//反转链表
ListNode* head = slow;
ListNode* n1 = NULL;
ListNode* n2 = head;
ListNode* n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;
}
//判断回文
ListNode* left = A;
ListNode* right = n1;
while(right)
{
if (left->val != right->val)
{
return false;
}
left = left->next;
right = right->next;
}
return true;
}
};这样在链表个数没被限制下，也能使空间复杂度降为O(1)，同时时间复杂度为O(n)。