讨论/题目交流/回文链表/
回文链表

判断一个链表是否是回文链表
我的思路是吧链表从中间分成pre1、pre2前后两部分,然后把后面的pre2反转,在遍历pre1\pre2判断是否每个结点的值都相等,如果都相等则是回文,否则不是。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n=0,m,i=1,flag=1;    
        ListNode *pre1=new ListNode(0);
        ListNode *pre2=new ListNode(-1);
        ListNode *p;
        p=head;
        pre1->next=head;
        while(p) {n++;p=p->next;}//n用来记录链表的节点个数、长度
        if(n==1) return true;
        
        m=n/2;
        while(i<m)//找到分界节点
        {
            i++;
            head=head->next;
        }
        
        if(n%2==0)  //把链表分为pre1和pre2两条链表
        { ***if(head->next) pre2->next=head->next;***//line 29 执行出错 
          head->next=NULL;
        }
        else{
            pre2->next=head->next->next;
            head->next=NULL;   //如果是奇数个节点,就把最中间的节点去掉
        }
        
        ListNode *first,*second;//把后面的链表pre2反转
        first=pre2->next;
        second=first->next;
       while(second)
        {
            first->next=second->next;
            second->next=pre2->next;
            pre2->next=second;
            second=first->next;
        }
        while(pre1->next&&pre2->next)//看pre1、pre2是否每一个节点的值都相同,判断是否是回文
        {
            if(pre1->next->val!=pre2->next->val) {flag=0;break;}
            pre1=pre1->next;
            pre2=pre2->next;
            
        }
        if(flag) return true;
        else return false;
    }
};

执行出错Line 29: Char 20: runtime error: member access within null pointer of type 'ListNode' (solution.cpp) 就是我注释的那一行出错,可是我为了防止引用空指针,还加了个判断语句,还是不可以,这是为什么呢?

共 1 个回复

直接递归找到尾节点,然后从头和尾一起走判断相不相等就可以了,搞这么麻烦。。。