Why can't my solution pass the case of [1,4,-1,-1,4,1].


  • -1
    X

    First I reverse the last half and then compare them. Below are codes:

    /**

    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
      
    • struct ListNode *next;
      
    • };
      /
      bool isPalindrome(struct ListNode
      head) {
      int length=0;
      struct ListNode*head2,*p,*q,*r;
      p=head;
      while(p!=NULL)
      {
      length++;
      p=p->next;
      }
      if(length<6)
      {
      if(length<2)
      return 1;
      if(length==2)
      return head->val==head->next->val;
      if(length==3)
      return head->val==head->next->next->val;
      if(length==4)
      return (head->val==head->next->next->next->val)&&(head->next->val==head->next->next->val);
      if(length==5)
      return (head->val==head->next->next->next->next->val)&&(head->next->val==head->next->next->next->val);
      }
      if(length%2)
      {
      head2=head;
      for(int i=0;i<length/2+1;i++)
      head2=head2->next;
      }
      else
      {
      head2=head;
      for(int i=0;i<length/2;i++)
      head2=head2->next;
      }
      p=head2;
      q=p->next;
      r=q->next;
      for(int i=0;i<length/2-2;i++)
      {
      q->next=p;
      p=q;
      q=r;
      r=r->next;
      }
      q->next=p;
      head2=q;
      bool flag=1;
      for(int i=0;i<length/2;i++)
      {
      if(head->val==head2->val)
      {
      head=head->next;
      head2=head2->next;
      }
      else
      {
      flag=0;
      break;
      }
      }
      return flag;
      }

  • 0

    @xingy12

    • your code is really complicated
    • format your code properly using ```

  • 0
    class Solution {
    public:
        bool isPalindrome(ListNode* head) 
        {
            if(!head || !head->next) return true;
            ListNode *slow = head, *fast = head->next, *next = NULL;
            while(fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            fast = slow->next;
            slow->next = NULL;
            ListNode newHead(0);
            newHead.next = fast;
            while(fast && fast->next)
            {
                next = fast->next;
                fast->next = fast->next->next;
                next->next = newHead.next;
                newHead.next = next;
            }
            fast = newHead.next;
            slow = head;
            while(slow && fast)
            {
                if(slow->val == fast->val)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                else return false;
            }
            return true;
        }
    };
    

Log in to reply
 

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