面试题 02.06. 回文链表
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2
输出： false
示例 2：
输入： 1->2->2->1
输出： true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
不要求空间复杂度
思路：
利用一个栈和双指针。
- 遍历的时候把值压入栈，快指针为空时结束。
- 慢指针遍历右半部分，比较当前值和栈顶值是否相等。
时间复杂度o(n)，空间复杂度o(1)
思路：
- 首先双指针找到链表中间和右链表的首结点，将一个链表分为左右两个链表。
若结点个数为奇数(1->2->3)，中间结点为2，右链表的首结点为 3。
若结点个数为奇数(1->2->3->4)，中间结点为2，右链表的首结点为 3。 - 翻转右链表
- 判断左右链表是否相同，相同也就是回文
- 还原右链表，并把左右链表连接。
/**
* 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) {
if(head==NULL||head->next==NULL)
return true;
ListNode* p1=head,*p2=head;
while(p2->next!=NULL&&p2->next->next!=NULL)
{
p1=p1->next;
p2=p2->next->next;
}//结束后 p1 为尾结点 p1->next为 链表右面第一个 结点
//将 单链表 分成两个单链表
ListNode* rigP=p1->next; //记录 右链表的第一个结点
p1->next=NULL;
//反转右链表
ListNode* rigPhead=NULL;
while(rigP!=NULL)
{
ListNode* tmp=rigP->next;
rigP->next=rigPhead;
rigPhead=rigP;
rigP=tmp;
}// 结束后 rigPhead 为新链表首结点 rigP为最右空结点
bool res=true; //初始化返回变量
// 进行比较
while(head!=NULL&&rigPhead!=NULL)
{
if(head->val!=rigPhead->val)
{
res=false;
break;
}
head=head->next;
rigPhead=rigPhead->next;
}
//再将右面链表复原 rigPhead 为右链表首结点 rigP 为最右空结点
while(rigPhead!=NULL)
{
ListNode* tmp=rigPhead->next;
rigPhead->next=rigP;
rigP=rigPhead;
rigPhead=tmp;
}// 结束后 rigP 为链表首结点
//将左链表尾连接到右链表首
p1->next=rigP;
return res;
}
};
时间复杂度 n/2+n/2+n+n/2=2.5n，也就是o(n)了。
这道题做的比较费劲，断断续续做了三天，期间一度不想看了，有点难顶，不过学到了利用虚拟头节点，以及搞懂了 p->next=q 和 q=p->next 的区别，希望再碰到链表的题目会趁手一些。
坚持才是胜利，加油，奥里给！
