C++ reverse second half of linked list, O(n) time O(1) space


  • 0
     bool isPalindrome(ListNode* head) {
            if(head==NULL||head->next==NULL) return true;
            ListNode* tail=head;
            ListNode* mid=head;
            //Find the mid node
            while(tail!=NULL&&tail->next!=NULL){
                mid=mid->next;
                tail=tail->next->next;
            }
            ListNode* pre,*cur,*next;
            pre=NULL;
            cur=mid;
            next=mid->next;
            //Reverse the second half of list
            while(cur!=NULL){
                cur->next=pre;
                pre=cur;
                cur=next;
                next=next==NULL?NULL:next->next;
            }
            //pre is the tail of the original list and now is the head of the reversed list
            while(pre!=NULL){
                if(pre->val!=head->val) return false;
                pre=pre->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.