Accepted C Solution Rt(N) Sp(1) and restored the list


  • 0
    R

    when come to single linked list,there are few primary operations you should always keep in mind,like reverse,merge,find certain node etc.then u can solve all the problems with a combination of these operations.

    bool isPalindrome(struct ListNode* head) {
    	if(!head || !head->next) return true;
    
    	struct ListNode *pslow=head;
    	struct ListNode *pfast=head->next;
    	struct ListNode *pp=NULL;
    	struct ListNode *pt=NULL;
    	struct ListNode *ph=NULL;
    
    	//reverse the first half
    	while(pfast && pfast->next){
    		pt=pslow->next;
    		pslow->next=pp;
    		pp=pslow;
    		pslow=pt;
    		pfast=pfast->next->next;
    	}
    	//odd or even
    	pt=pslow->next;
    	if(pfast){
    		pslow->next=pp;
    		head=pslow;
    		ph=pt;
    	}else{
    		head=pp;
    		ph=pslow;
    	}
    	//restore and judge
    	bool res=true;
    	while(head){
    		if(res && head->val!=pt->val){
    			res=false;
    		}
    		pp=head->next;
    		head->next=ph;
    		ph=head;
    		head=pp;
    		pt=pt->next;
    	}
    
    	return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.