Palindrome Linked List C++ fast solution


  • 1
    P
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            
            if(!head || !head->next) return true;
        	
        	// Determine the size of the list
        	int listSize = 0;
        	for(ListNode * tmp = head; tmp != NULL; tmp = tmp->next)
        		listSize++;
        
        	int nbShift = listSize / 2;
        	if(listSize % 2)
        		nbShift++;
        	
        	ListNode * secondHead = head;
        	for(int i = 0; i < nbShift; i++)
        		secondHead = secondHead->next;
        
        	secondHead = reverseLinkedList(secondHead);
        
        	for(int i = 0; i < listSize - nbShift; i++)
        	{
        		if(head->val != secondHead->val)
        			return false;
        		else
        		{
        			head = head->next;
        			secondHead = secondHead->next;
        		}
        	}
        
        	return true;
        }
        
        ListNode *  reverseLinkedList(ListNode* head)
        {
        	if(!head || !head->next) head;
        
        	ListNode * tmp = NULL;
        	ListNode * prevNode = head;
        	ListNode * currNode = head->next;
        	head->next = NULL;
        
        	while(currNode)
        	{
        		tmp = currNode->next;
        		currNode->next = prevNode;
        		prevNode = currNode;
        		currNode  = tmp;
        	}
        
        	return prevNode;
        }
    };

Log in to reply
 

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