My accepted C++ solution


  • 0
    Y
        class Solution {
        public:
            bool isPalindrome(ListNode* head) {
                if (!head || !(head->next))return true;
            	ListNode *p = head;
            	int l_size = 0;
            	while (p)
            	{
            		++l_size;
            		p = p->next;
            	}
            	int half_size = l_size % 2 == 0 ? l_size / 2 : l_size / 2 + 1;
                //make p-pointer point to the second part of the list
            	for (l_size = 0, p = head; p && l_size < half_size; ++l_size, p = p->next){}
                //get the second part reversed
            	ListNode *list_keep = list_reverse(p);
            	ListNode *pre = head, *q = list_keep;
            	bool flag = true;
                //make the first part compare with the second part one by one
            	for (l_size = 0, p = head; q && l_size < half_size; ++l_size, p = p->next, q = q->next)
            	{
            		pre = p;
            		if (p->val != q->val)
            		{
            			flag = false;
            			break;
            		}
            	}
                //make sure that the pre-pointer points to the last element of the first part
            	while (l_size < half_size)
            	{
            		pre = p;
            		++l_size;
            		p = p->next;
            	}
                //get the second part reversed again and restore the list
            	pre->next = list_reverse(list_keep);
            	return flag;
            }
        private:
            ListNode *list_reverse(ListNode *head)
            {
            	if (!head || !(head->next))return head;
            	ListNode *first = new ListNode(-1);
            	while (head)
            	{
            		ListNode *keep = head->next;
            		head->next = first->next;
            		first->next = head;
            		head = keep;
            	}
            	head = first->next;
            	delete first;
            	return head;
            }
        };

  • 0

    Good solution but the style is too long and too complicated


Log in to reply
 

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