【LeetCode】234. Palindrome Linked List

问题描述

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

问题分析

使用快慢指针找到中点，然后将后半截链表逆置，再将后半截与前半截进行比较，如果有一个数不相等则返回false；否则返回true。

代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* fast = head;
		ListNode* slow = head;
		if(head==0) return 1;
		// 使用快慢指针确定中点 
		while(slow->next&&fast->next&&fast->next->next) {
			slow = slow->next;
			fast = fast->next->next;
		}
		slow = slow->next;
		// 逆置后半截
		ListNode* p = slow;
		ListNode* q;
		while(p&&p->next) {
			q = p->next;
			p->next= p->next->next;
			q->next= slow;
			slow = q;
		}
		p = head;
		q = slow;
		while(p&&q) {
			if(p->val!=q->val) return false;
			q=q->next;
			p=p->next;
		}
		return true;
    }
};