Share my c++ solution with explanation


  • 0
    W
    bool isPalindrome(ListNode* head) {
            if (!head)
                return true;
            // find the middle node
            ListNode *slow = head;
            ListNode *fast = head;
            while(fast && fast->next)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
            //modify the list: e.g.,
            //1->2->3->4 ==> 1->2->3<-4
            //1->2->3->4->5 ==> 1->2->3<-4<-5
            ListNode *pre = slow;
            ListNode *post = slow->next;
            slow->next = nullptr;
            ListNode *temp;
            while(post)
            {
                temp = post->next;
                post->next = pre;
                pre = post;
                post = temp;
            }
            //examine if it satisfy the Palindrome requirements
            ListNode *tail = pre;
            while(tail != head && tail && head)
            {
                if (tail->val != head->val)
                    return false;
                tail = tail->next;
                head = head->next;
            }
            return true;
        }

Log in to reply
 

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