[LeetCode]Palindrome Linked List

不允许我们用额外的空间，那么stack和递归都不能用。我们只好reverse linkedlist的后一半，然后进行比较。时间复杂度O(n)，常数空间，代码如下：

	/**
	* 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)return true;
	ListNode* slow = head, *fast = head;
	while(fast->next != nullptr && fast->next->next != nullptr)
	{
	fast = fast->next->next;
	slow = slow->next;
	}
	//even length
	if(fast->next)
	{
	fast = fast->next;
	slow = slow->next;
	}
	//rever second half
	ListNode* before = slow;
	slow = slow->next;
	before->next = nullptr;
	while(slow)
	{
	ListNode* after = slow->next;
	slow->next = before;
	before = slow;
	slow = after;
	}
	//check if palindrome
	while(fast && head)
	{
	if(fast->val != head->val)
	return false;
	fast = fast->next;
	head = head->next;
	}
	return true;
	}
	};

view raw Palindrome Linked List.cpp hosted with ❤ by GitHub