leetCode Q234: 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?

Solution:

You have to change the structure of the linked list to have a O(n) time and O(1) space algorithm. Idea: locate the middle node of the list, reverse the first half of the list. This is not easy at all, need to be very careful when counting steps.

	/**
	* 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* p0=head;
	ListNode* p1=head;
	int steps=0;
	while(p0){p0=p0->next;steps++;}
	if(steps%2!=0)
	for(int i=0; i<steps/2+1; i++)
	p1=p1->next;
	else
	for(int i=0; i<steps/2; i++)
	p1=p1->next;
	p0=head;
	ListNode* np = p0->next;
	p0->next=NULL;
	for(int i=0; i<steps/2-1; i++){
	ListNode* tmp=np->next;
	np->next=p0;
	p0=np;
	np=tmp;
	}
	while(p0&&p1){
	if(p0->val!=p1->val)
	return false;
	p0=p0->next;
	p1=p1->next;
	}
	return true;
	}
	};

view raw Q234PalindromeLinkedList.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* 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* p0=head, *p1=head;
	while(p1->next!=NULL&&p1->next->next!=NULL){
	p0=p0->next;
	p1=p1->next->next;
	}
	ListNode* cur = p0->next;
	ListNode* pre = NULL;
	ListNode* next = NULL;
	p0->next=NULL;
	while(cur!=NULL){
	next = cur->next;
	cur->next = pre;
	pre = cur;
	cur = next;
	}
	p0 = head;
	p1 = cur==NULL? pre:cur;
	while(p0!=NULL&&p1!=NULL){
	if(p0->val!=p1->val)
	return false;
	p0=p0->next;
	p1=p1->next;
	}
	return true;
	}
	};

view raw Q234Rnd2.cpp hosted with ❤ by GitHub